今天做了一道题，要用判断一个字符串是否是另一个字符串的子串，于是查了一下strstr的实现。
代码如下：
char *strstr(const char*s1,const char*s2)
{
const char*p=s1;
const size_t len=strlen(s2);
for(;(p=strchr(p,*s2))!=;p++)
{
if(strncmp(p,s2,len)==)
return (char*)p;
}
return();
}
从上面的GCC中strstr实现代码可以分析出，strstr的时间复杂度是O(n2)的(因为strncmp是O(N)的)，不过对长字符串匹配子串上可以采用kmp算法来提高效率（时间复杂度为O(m+n)），这里翻出了自己以前写的kmp算法的接口放到这里和大家分享一下，之前我也写过一篇关于kmp匹配子串的一篇文章，也可以去看一下。
这是我之前写的关于kmp介绍的文章地址:http://www.cnblogs.com/daimadebanyungong/p/4756853.html
下面是我翻出来的很早之前写的一个C版本的kmp算法的实现接口，欢迎纠正错误和分享经验。
#include <string.h>
#include <stdio.h> #define LIB_MATCH_NUM 5
#define LIB_STRING_LEN 40 char lib_match[LIB_MATCH_NUM][LIB_STRING_LEN] =
{
"www.baidu.comw",
"www.google.com",
"www",
"baidu.com",
"lualu",
}; int lib_match_len[LIB_MATCH_NUM]; int lib_match_next[LIB_MATCH_NUM][LIB_STRING_LEN + ] = {}; void get_next(); void lib_match_init()
{
memset(lib_match_len,,sizeof(lib_match_len));
int i;
for(i = ; i < LIB_MATCH_NUM; i++)
{
lib_match_len[i] = strlen(lib_match[i]);
} get_next(); // init next array
} void get_next()
{
int i,j,k; for(i = ; i < LIB_MATCH_NUM; i++)
{ lib_match_next[i][] = ;
lib_match_next[i][] = ; k = ; //point to the last next[j]
int len = lib_match_len[i]; for( j = ; j < len; j++)
{//j start from 1 because next start from 2
k = lib_match_next[i][j]; //k = next[j]; while(k > && lib_match[i][j] != lib_match[i][k])
{
k = lib_match_next[i][k];
} if(lib_match[i][j] == lib_match[i][k])
{//s[j] == s[next[k]] next[i+1] = next[k] +1
k++;
} lib_match_next[i][j+] = k;
} } } int lib_search(char *orignal,int len)
{
if(orignal == NULL)
{
return ;
} int i,j,k; for(i = ; i < LIB_MATCH_NUM; i++)
{
char *tmp = orignal; // match each model need to start from the first
k = ; // k start from the last next array for(j = ; j < len; j++)
{ while( k > && tmp[j] != lib_match[i][k])
{
k = lib_match_next[i][k];
} if(tmp[j] == lib_match[i][k])
{
k++;
} if(k == lib_match_len[i])
{
printf("match the model string %d : %s\n", i,lib_match[i]);
printf("match at the position :%d\n\n", j - lib_match_len[i] + ); // here can return the i to know which model string have been matched k = lib_match_next[i][k]; //to match another this model string
} } } return ;
} void print_next()
{
int i,j; for(i = ; i < LIB_MATCH_NUM; i++)
{
printf("model string : %s \n",lib_match[i]);
printf("next array:");
for(j = ; j < lib_match_len[i]+;j++)
{
printf(" %d",lib_match_next[i][j]);
}
printf("\n\n");
}
} int main()
{
char orignal[]; lib_match_init(); print_next(); while()
{ scanf("%s",orignal); if(strcmp(orignal,"") == )
{
return ;
} lib_search(orignal,strlen(orignal));
} return ; }