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
     
      =m)return i;	}					return -1;	}
     

　　

int index2(string s, string t){	int n=s.length();	int m=t.length();	int i,j;	while((i
     
      =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
     

　　现在让我们来看看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

　　以下为优化代码，有的地方可以称次next数组为nextvalue数组

void CalcNext(string p, int next[]){	int n=p.length();	next[0]=-1;	int k=-1;	int j=0;	while(j