1.串的定义
由0个或者多个字符串组成的有限序列，又称为字符串。
2.串的抽象数据结构
ADT 串
Data
串的元素仅由字符组成，相邻元素具有前驱和后继关系。
Operation
Index(S,T,pos)//查找子串
Replace(S,T,V);//替代
等等
串这一章中，最重要的就是KPM（看毛片）算法的掌握和理解！！！
3.朴素的模式匹配算法
这里假设主串S的长度存储在S[0]中，子串T的长度存储在T[0]中，
因为T[0]和S[0]存储的是长度，所以实际字符从T[1]和S[1]开始
回溯的时候：
i=i-j+2;//回到首次匹配的下一个位置(如果从0开始，i=i-j+1)
j=1;//子串从第一个位置开始匹配 (如果从0开始，j=0)
//返回子串T在主串S从第pos个字符之后匹配的位置，不存在返回0
int Index(String S,String T,int pos)
{
int i = pos;//从第pos个字符之后开始匹配
int j = 1;//子串从第一个字符开始匹配
while(i<=S[0] && j<=T[0])//主串没有结束，且子串没到末尾时候
{
if(S[i]==T[i])
{
i++;//继续往下匹配
j++;
}
else
{
i=i-j+2;//回到首次匹配的下一个位置
j=1;//子串从第一个位置开始匹配
}
if(j>T[0])//如果完全匹配上了，j就会>T[0]至少一个长度
return i-T[0];
else
return 0;
}
}
4.KMP模式匹配算法
参考文章：
1. 详解KMP算法
2. KMP原理、分析及C语言实现
3.小甲鱼-KMP算法视频详解
小甲鱼的视频讲的蛮清晰的，静下心来看，跟着小甲鱼思考，就能弄懂这个KMP算法！
其实KMP算法的核心就在于next数组，弄懂这个数组，就弄明白KMP算法了。
这个next数组，就是指在子串T（也称为模式串T）匹配失败后，j应该回溯到哪个位置继续匹配。
next的值取决于前缀和后缀有几个相同的字母。
next的值 = 最大前缀和后缀相同的字母 + 1
next数组详解
T[0]=9,表示数组的长度。
j表示当前T串下标
前缀：必须包含第一个字母，且不包含最后一个字母
后缀：必须包含最后一个字母，且不包含第一个字母
当j=1时，1到j-1没有任何字母，next[1]=0
当j=2时，1到j-1字母为a,没有前缀和后缀，next[2]=0+1=1
当j=3时，1到j-1字母为ab,前缀：a,后缀：b，没有相同的字母next[2]=0+1=1
当j=4时，1到j-1字母为aba,前缀:a 后缀：a ，有1个相同的字母，next[2]=1+1=2
当j=5时，1到j-1字母为abab,前缀:ab 后缀：ab ，有2个相同的字母，next[2]=2+1=3
当j=6时，1到j-1字母为ababa,前缀:aba 后缀：aba ，有3个相同的字母，next[2]=3+1=4
当j=7时，1到j-1字母为ababaa,前缀:a 后缀：a ，有1个相同的字母，next[2]=1+1=2
当j=8时，1到j-1字母为ababaaa,前缀:a 后缀：a ，有1个相同的字母，next[2]=1+1=2
当j=9时，1到j-1字母为ababaaab,前缀:ab 后缀：ab ，有2个相同的字母，next[2]=1+1=3
得到下面表格:
| 模式串T | 9 | a | b | a | b | a | a | a | b | a |
|---|---|---|---|---|---|---|---|---|---|---|
| 下标j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| next数组 | ^ | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 |
这里定义i和j
i:表示后缀的位置
j:表示前缀的位置
当
i=3，j=1,T[3]=T[1]=a
此时：i和j都应+1，i++=4,j++=2,
而前缀=a,后缀=a,最大相同前缀为1，
next[i]=1(最大相同前缀和后缀)+1=2,此时j也等于2，因此next[i]=j
当i=4,j=2,T[4]==T[2]=b
此时：i和j都应+1，i++=5,j++=3,
而前缀=ab,后缀=ab,最大相同前缀为2，
next[i]=2(最大相同前缀和后缀)+1=3,此时j也等于3，因此next[i]=j
当i=5,j=3,T[5]==T[3]=a
此时：i和j都应+1，i++=6,j++=4,
而前缀=aba,后缀=aba,最大相同前缀为3，
next[i]=3(最大相同前缀和后缀)+1=4,此时j也等于4，因此next[i]=j
T[i]==T[j]情况下，翻译成代码:
if(T[i]==T[j])
{
i++;
j++;
next[i]=j;
}
当i=6,j=4,T[6]=a,不等于T[4]=b
此时：j应该回溯,那么应该回溯到哪个位置呢？
回顾一下next数组
1.next数组的含义:当模式串T匹配失败时，next数组的值指导应该回溯到T串的哪个位置开始下一轮的匹配
2.当i=6时，T串为"ababaa,我们当做母串，j=4，T串为"abab,我们当做子串
3.在1和2的基础上，我们思考一下在哪里匹配失败了，在j==4的时候匹配失败了是吧，那失败之后，next数组就来指导下一轮的匹配，
因此 j==next[j]==next[4]=2，从j串的第2个位置开始下一轮匹配
T[i]不等于T[j]情况下，翻译成代码:
else
{
j=next[j]；//j回溯
}
另外，无论什么模式串T，next[1]==0，永远为0，因为没有任何前缀和后缀嘛！
next[1]=0;
获得next数组的代码
int i=1;//i表示后缀，所以从1开始
int j=0;//j表示前缀，所以从0开始(数组的第一位是0呀)
T[0]存储模式串T的长度
注意:由于T[0]存储的是长度，因此没必要判断T[0]是否和T[1]相等，
所以当j=0的时候，
i++=2;//第二个字符
j++=1;//第一个字符
next[i]=next[2]=1;和表格的相同
void get_next(String T,int *next)
{
int i=1;//i表示后缀，所以从1开始
int j=0;//j表示前缀，所以从0开始(数组的第一位是0呀)
next[1]=0;//无论什么模式串T，next[1]==0，永远为0，因为没有任何前缀和后缀嘛！
while(i<T[0])//当i小于模式串T的长度时
{
//由于T[0]存储的是长度，因此没必要判断T[0]是否和T[1]相等，直接往后判断
if(j==0 || T[i]==T[j])
{
i++;
j++;
next[j]=j;
}
else
{
j=next[j];//j回溯
}
}
}
KMP算法的实现
其实KMP算法和之前的朴素算法最大的不同就是这个next数组，避免不必要的回溯。
//返回子串T在主串S从第pos个字符之后匹配的位置，不存在返回0
int Index_KMP(String S,String T,int pos)
{
int i = pos;//从第pos个字符之后开始匹配
int j = 1;//子串从第一个字符开始匹配
int next[255];//用于保存next数组
get_next(T,next);//对T串分析，获得next的值
showNext(next,T[0]);//打印一下next的值
while(i<=S[0] && j<=T[0])//i<主串S的长度，且j<子串T的长度，继续循环
{
//j==0，直接++，从第一个位置开始比较,
if(j==0 || S[i]==T[j])//S[i]=T[j]，继续往下比较
{
i++;
j++;
}
else//匹配失败，则从next数组获得下一轮T串应该从哪个位置开始比较
{
j=next[j];
}
}
if(j>T[0])//说明T串匹配完毕
{
printf("j=%d,T[0]=%d 匹配成功,从第%d个位置开始完成匹配\n",j,T[0],i-T[0]);
return i-T[0];
}
else
{
printf("匹配失败\n");
return 0;
}
}
KMP算法的终极优化
假设S="aaaabcde",T="aaaaax",next=012345,因为前面的a是相同的，因此没必要从5回溯到4在回溯到3...最后到0去比较
void get_next(String T,int *next)
{
int i=1;//i表示后缀，所以从1开始
int j=0;//j表示前缀，所以从0开始(数组的第一位是0呀)
next[1]=0;//无论什么模式串T，next[1]==0，永远为0，因为没有任何前缀和后缀嘛！
while(i<T[0])//当i小于模式串T的长度时
{
//由于T[0]存储的是长度，因此没必要判断T[0]是否和T[1]相等，直接往后判断
if(j==0 || T[i]==T[j])
{
i++;
j++;
if(T[i]!=T[j])//当i和j++后，如果T[i]和前缀T[j]不同
next[j]=j;
else//否则，直接去next[j]的值
next[j]=next[j];
}
else
{
j=next[j];//j回溯
}
}
}
到此，KPM算法毕业！！！
完整源码
S串： " ababababcababaaabaddd";
T串：" ababaaaba";
#include <stdio.h>
#include <windows.h>
typedef char* String;
void get_next(String T,int *next)
{
int i=1;
int j=0;
next[1]=0;
while(i<T[0])
{
if(j==0 || T[i]==T[j])
{
i++;
j++;
if(T[i]!=T[j])
next[i]=j;
else
next[i]=next[j];
}
else
{
j=next[j];//j回溯
}
}
}
//打印数组的值
void showNext(int *next,int len)
{
int i=1;
printf("next的值为：");
while(i<=len)
{
printf("%d ",next[i]);
i++;
}
printf("\n");
}
//返回子串T在主串S从第pos个字符之后匹配的位置，不存在返回0
int Index_KMP(String S,String T,int pos)
{
int i = pos;//从第pos个字符之后开始匹配
int j = 1;//子串从第一个字符开始匹配
int next[255];//用于保存next数组
get_next(T,next);//对T串分析，获得next的值
showNext(next,T[0]);//打印一下next的值
while(i<=S[0] && j<=T[0])//i<主串S的长度，且j<子串T的长度，继续循环
{
if(j==0 || S[i]==T[j])//j==0，直接++，从第一个位置开始比较，
{ //因为T[0]和S[0]存储的长度
i++;
j++;
}
else//匹配失败，则从next数组获得下一轮T串应该从哪个位置开始比较
{
j=next[j];
}
}
if(j>T[0])//说明T串匹配完毕
{
printf("j=%d,T[0]=%d 匹配成功，从第%d个位置开始完成匹配\n",j,T[0],i-T[0]);
return i-T[0];
}
else
{
printf("匹配失败\n");
return 0;
}
}
int main()
{
char S[255] = " ababababcababaaabaddd";
S[0]=18;
char T[255] = " ababaaaba";
T[0]=9;
Index_KMP(S,T,1);
system("pause");
return 1;
}
