本文共 886 字，大约阅读时间需要 2 分钟。

字符串是由0个或多个字符构成的序列，可记为s='a1a2a3…an'，其中ai可以是字母，也可是数字或者其他字符，零个字符的串称为空串。

而字符串的顺序结构就是用简单的char类型数组来存储没什么好说的，下面介绍一下BF算法与KMP算法：

BF算法就是比较平常的双重循环，如果匹配成功打断循环，否则子串的比较开始数加一，函数：

int BF(char s[],char t[])

{ int start=0; int i=0,j=0; while((s[i]!='\0')&&(t[j]!='\0')) {     if(s[i]==t[j]) {i++;j++;}     else {start++;i=start;j=0;} } if(t[j]=='\0') return start+1; else return 0; }

相比较于BF算法，KMP算法减少了回溯的过程，这样大大提高了代码效率，它的思想就是找到副串当中，当前位置的字符与要匹配的串前面有多少相同的字符，这样就可以直接和相同之后的字符匹配，大大减少了时间复杂度。

借张图表示一下每个表示有多少相同字符的数组计算方法：

具体实现代码：

void Next(char *t,int *nv,int size)        

{     int i=1,j=0;     nv[1]=0;     while(i<size)     {         if(j==0||t[i]==t[j])                          {             ++i;++j;             nv[i]=j;                                }         else             j=nv[j];            } } int KMP(char *s,char *t,int pos,int size1,int size2)   {     int i=pos,j=1;     int *next=new int[size2];     next[0]=size2;     Next(t,next,size2);                             while(i<size1&&j<size2)                                {         if(j==0||s[i]==t[j])         {i++;j++;}         else         j=next[j];     }     if(j>=size2)         return i-size2+1;                           else         return 0;                               }