1、Definition
串string，是零个或多个字符组成的有限序列。一般记作S="a1a2a3...an"，其中S是串名，双引号括起来的字符序列是串值；ai（1<= i <=n）可以是字母、数字或其他字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串（Empty String），不包含任何字符。
2、
子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串有被称为该子串的主串。
子串的位置：子串在主串中第一次出现的第一个字符的位置。
两个串相等：两个串长度相等，并且各个对应的字符也都相等。
3、串的模式匹配算法
串的匹配实际上是对与合法的位置1<= i <=n-m+1，依次将目标串中的子串S[i..i+m-2]和模式串T[1..m-1]进行比较，若S[i..i+m-2]=T[1..m-1]，则称从位置i开始的匹配成功，亦称模式T在目标S中出现：若S[i..i+m-2]!=T[1..m-1]，则称从位置i开始的匹配失败。
其算法段为：
for(i=1; i<=n-m+1; i++) if(S[i..i+m-2]=T[1..m-1]) return i;
int index1(string s, string t)
{
int n=s.length();
int m=t.length();
for(int i=0;i<n-m; i++)
{
int j=0;
int k=i;
while(j<m && s[k]==t[j])
{
k++;
j++;
}
if(j>=m)return i;
}
return -1;
}
int index2(string s, string t)
{
int n=s.length();
int m=t.length();
int i,j;
while((i<n) && (j<m))
{
if(s[i]==t[j])
{
i++;
j++;
}
else
{
i=i-j+1;
j=0;
}
}
if(j>=m)return i-j;
else return -1;
}
4、KMP算法
在3中我们看到的是模式匹配的暴力求解法，这种算法虽然能够得到结果，但问题是，这个算法的时间复杂度为O(M*N)，效率不高，为了解决这个问题，KMP三人对此做出了改进，提出了KMP算法。
详细描述：
在一般的暴力求解法中，当文本串第i个字符与模式串第j个字符不匹配时，文本串往往会回溯到i-j+1处，而模式串会回溯到0处，在KMP算法中却不用进行这样的回溯，
当发生失配时，我们通过拉动模式串进行不回溯的检查，当文本串第i个字符与模式串第j个字符不匹配时，模式串会跳转到next[j]值所在的位置再继续比较（next[j]是啥？莫急，稍后解释），如果next[j]只是-1，那么只能从模式串开始来比较了。
KMPcode
int KMP(string s, string t, int next[])
{
int i=0;
int j=0;
int n=s.length();
int m=t.length();
while((i<n)&&(j<m))
{
if(j=-1||s[i]==t[j])
{
i++;
j++;
}
else
j=next[j];
}
if(j==m)return i-j;
else return -1;
}
现在让我们来看看next是啥子玩意
next是一个数组，是一个模式函数值，对于每一个模式串的每一个字符可能会存在最大k个前缀与k个后缀相等，则字符的next值为k个前缀的下一个字符的index，对于第一个字符来说它的next值就为-1，以下贴出求数组代码
void CalcNext(string s, int next[])
{
int n=s.length();
next[0]=-1;
int k=-1;
int j=0;
while(j<n)
{
if(k==-1||s[j]==s[k])
{
++k;
++j;
next[j]=k;
}
else
k=next[k];
}
}
以下为优化代码，有的地方可以称次next数组为nextvalue数组
void CalcNext(string p, int next[])
{
int n=p.length();
next[0]=-1;
int k=-1;
int j=0;
while(j<n)
{
if(k==-1||p[j]==p[k])
{
++k;
++j;
if(p[j]==p[k])
next[j]=next[k];
else
next[j]=k;
}
else
{
k=next[k];
}
}
}