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;
}