串的模式匹配算法：
通俗讲：给字串定位

简单模式匹配算法
KMP算法

简单模式匹配算法
通俗讲：大串A，小串B，这俩目前没啥关系，现在就想知道小串B是不是在包含在大串A里

结果判定：

匹配上：返回小串B在大串A里的位置。
没匹配上：返回标记

概念术语：模式串：小串B
KMP算法
利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置。

  串(又称字符串)是由n(n≥0)个字符组成的有限序列，它是数据元素为单个字符的特殊线性表。串可以用顺序存储方式或者链式存储方式进行存储。模式匹配是串最重要和最复杂的一个操作，其实也就是串的查找，其中Brute-Force算法和KMP算法是两种最经常使用的顺序存储结构下的串的模式匹配算法。

  模式匹配操作的具体含义是：

  在主串（也称做目标串)S中，从位置start开始查找是否存在子串(也称做模式串)T，如果在主串S中查找到一个与模式串T相同的子串，则称查找成功；如在主串S中未找到一个与模式串T相同的子串，则称查找失败。当模式匹配成功时,函数返回模式串T的第一个字符在主串S中的位置;当模式匹配失败时,函数返回-1。

  实际上，这就是C语言的 strstr() 以及 Java的 indexOf()函数实现的功能。

Brute-Force算法
  BF算法的主要思想是：将主串S的第start个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符起，重新与T第一个字符比较，直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值 –1。
    代码实现：
    public int BFindex(String S,int start,String T){
        int i=start,j=0,v;
        while(i<S.length() && j<T.length()){
            if(S.charAt(i)==T.charAt(j)){
                i++;
                j++;
            }
            else{
                i=i-j+1; //i的下一个，已经比较了j次，所以是i-j+1
                j=0;
            }
        }
        if(j==T.length()) //匹配成功
            v=i-j;
        else v=-1; //匹配失败
        return v;
    }

  例如，主串T为：ababcabababab,子串为ababa,上述过程如下图所示。


KMP算法
  BF算法简单并且容易理解，但是有些情况下时间效率不高，最好情况下（一配就中）时间复杂度为O(m)，最坏情况下时间复杂度为O(n×m)。

  为了克服主串下标i在若干个字符序列比较相等后，只要有一个字符比较不相等便需要把下标i的值回退的缺点，提出了改进的匹配算法KMP。

  KMP算法的主要思想是：利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置，重点就在于当某一个字符与主串不匹配时，我们应该知道j指针要移动到哪里。

  这可以分为两种情况来考虑：当前si和tj比较不相等，（1）当模式串中不存在可相互重叠的真子串，下一次可直接比较si和t0；（2）当模式串中存在可相互重叠的真子串时，j要移动的下一个位置为k，k满足：模式串中最前面的k个字符和j之前的最后k个字符是一样的。

  所以，问题的重点：计算每一个位置j对应的k，所以用一个数组next来保存，next[j] = k，表示当S[i] != T[j]时，j指针的下一个位置。
    求next的函数设计：
    public void getNext(String T,int[] next){
        next[0]=-1; //特殊值
        int j=0,k=-1;

        while(j<T.length()-1){
            if(k==-1 || T.charAt(j)==T.charAt(k))
                next[++j]=++k;
            else
                k=next[k];
        }
    }




  当next数组求出后，KMP算法实现也就比较容易，具体代码如下：
    public int KMP(String S,int start,String T,int [] next){
        int i=start,j=0,v;
        while(i<S.length() && j<T.length()){
            if(S.charAt(i)==T.charAt(j)){
                i++;
                j++;
            }
            else if(j==0) i++;
            else j=next[j];
        }
        if(j==T.length()) 
            v=i-j;
        else v=-1;
        return v;
    }



相关链接
详解KMP算法

字符串的模式匹配

子串的定位运算通常称为串的模式匹配或串匹配。

串的模式匹配设有两个字符串S和T，设S为主串，也称正文串；设T为子串，也称模式。在主串S中查找与模式T相匹配的子串，如果匹配成功，确定相匹配的子串中的第一个字符在主串S中出现的位置。


著名的模式匹配算法有BF算法和KMP算法，下面介绍BF算法。

模式匹配不一定是从主串的第一个位置开始，可以指定主串中查找的起始位置pos。



【算法步骤】

①分别利用计数指针 i 和 j 指示主串 S 和模式 T 中当前正待比较的字符位置，i 初值为pos， j 初值为1。

②如果两个串均未比较到串尾，即 i 和 j 分别小于等于 S 和 T 的长度时，则循环执行以下操作：

S.ch[i] 和 T.ch[j] 比较，若相等，则 i 和 j 均分别指示串中下个位置，继续比较后续字符
若不等，指针后退重新开始匹配，从主串的下一个字符（i=i-j+2）起再重新和模式的第一个字符（j=1）比较

③如果j >T.length，说明模式 T 中的每个字符依次和主串 S 的一个连续的字符序列相等，则匹配成功，返回和模式 T 中第一个字符相等的字符在主串 S 中的序号（i-T.length）；否则称匹配不成功，返回0。
【算法描述】
int Index_BF(SString S,SString T,int pos)
{//返回模式T在主串S中第pos个字符开始第一次出现的位置。若不存在，则返回值为0
 //其中，T非空，1 ≤pos≤ S.length
 i=pos; j=1;               //初始化
   while( i<=S.length && j<=T.length)   //两个串均未比较到串尾
   { 
     if(S.ch[i]==T.ch[j])
       {++i;++j;}                      //继续比较后续字符
     else
       {i=i-j+2;j=1;}                  //指针后退重新开始比较
   }
 if(j>T.length)  return i-T.length;    //匹配成功
 else return 0;                        //匹配失败
 }      

【算法分析】

①最好情况下O(n+m)，每趟不成功的匹配都发生在模式串的第一个字符与主串中相应字符的比较，例如：

S=“aaaaaba”

T=“ba”

②最坏情况下O(n×m)，每趟不成功的匹配都发生在模式串的最后一个字符与主串中相应字符的比较，例如：

S=“aaaaaab”

T=“aab”

代码实现：
#include<stdio.h>
#include<string.h>
int lens,lent;
int Index_BF(char s[],char t[],int pos)
{
   int i=pos; int j=1;               //初始化
   while( i<=lens && j<=lent)   //两个串均未比较到串尾
   { 
     if(s[i]==t[j])
       {++i;++j;}                      //继续比较后续字符
     else
       {i=i-j+2;j=1;}                  //指针后退重新开始比较
   }
 if(j>lent)  return i-lent;    //匹配成功
 else return 0;                        //匹配失败
 }     
 
int main()
{
	char s[100],t[100];
	int x,i;
	gets(s);
	gets(t);
	lens=strlen(s);
	lent=strlen(t);
	for (i=lens;i>0;i--)  //将主串所有元素全部后移
	{ 
	  s[i]=s[i-1]; 
	} 
	  for (i=lent;i>0;i--)  //将子串所有元素全部后移
	{ 
	  t[i]=t[i-1]; 
	} 
	x=Index_BF(s,t,1);
	printf("%d",x);
	//return 0;
} 


这个是关于KMP算法的讲解KMP算法—串的模式匹配算法

借鉴：《数据结构》 严蔚敏

串的模式匹配也称为子串的定位操作，即查找子串在主串中出现的位置。它是经常用到的一个算法，也是数据结构中的一个难点之一。串的模式匹配算法常见的有两种：Brute-Force朴素模式匹配算法和KMP算法。

【Brute-Force算法】

子串的定位操作串通常称为模式匹配，是各种串处理系统中最重要的操作之一。设有主串S和子串T，如果在主串S中找到一个与子串T相等的串，则返回T的第一个字符在串S中的位置。其中，主串S又称为目标串，子串T又称为模式串。

Brute-Force算法的思想是：从主串S=“s0s1s2...sn-1”的第pos个字符开始与模式串T=“t0t1t2...tm-1”的第一个字符进行比较，如果相等则继续逐个比较后续字符；否则从主串的下一个字符开始重新与模式串T的第一个字符进行比较，依此类推。如果在主串S中存在与模式串T相等的连续字符序列，则匹配成功，函数返回模式串T中第一个字符在主串S中的位置；否则返回-1表示匹配失败。

假设主串S="ababcabcacbab"模式串T="abcac",S的长度n=13,T的长度m=5。用变量i表示主串S当前正在比较字符的下标，变量j表示子串T中当前正在比较字符的下标。模式匹配的过程如图



【BMP算法】

KMP算法是由D.E.Knuth、J.H.Morris、V.R.Pratt共同提出的，因此被称为KMP算法（Knuth-Morris-Pratt算法）。KMP算法在Brute-Force算法的基础上有较大的改进，可在O(n+m)时间数量级上完成串的模式匹配，主要是消除了主串指针的回退，使算法效率有了很大的程度的提高。

根据Brute-Force算法，遇到不相等的字符，将子串后移一位，再从头逐个比较。这样做虽然可行，但是效果很差，因为你要将主串和子串的指针都退回到原来的位置，将已经比较过的字符重新比较一遍。

KMP算法思想是：在每一趟匹配过程中出现字符不等时，不需要回退主串的指针，而是利用已经得到前面“部分匹配”的结果，将模式串向右滑动若干个字符后，继续与主串中的当前字符进行比较。

假设主串S="ababcabcacbab"模式串T="abcac"。KMP算法匹配过程如图



 

从图中可以看出，KMP算法的匹配次数从原来的6趟减少为3趟。而对于Brute-Force算法，在第3趟匹配过程中，当i=6,j=4时，主串中的字符与模式串中的字符不相等，又从i=3,j=0开始比较。经过仔细观察，其实在i=3,j=0,i=4,j=0,i=5,j=0这三次比较过程都是没有必要的。因为从第3趟的部分匹配课得出：S2=T0='a',S3=T1='b',S4=T2='c',S5=T3='a',S6≠T4,因为S3=T1且T0≠T1,所以S3≠T0，所以没有必要从i=3、j=0开始比较。又因为S4=T2,且T0≠T2，故S4≠T0，所以S4与T0也没有必要从i=4、j=0开始比较。又因为S5=T3且T0=T4，故S5=T0,所以也没有必要将S5与T0进行比较。



也就是说，根据第3趟的部分匹配也可以得出结论：Brute-Force算法算法的第4、5趟是没有必要的，第6趟也没有必要将主串的第6个字符与模式串的第1个字符比较。





因此，只需要将模式串向右滑动3个字节，从i=6，j=1开始比较。同理，在第1 趟匹配的过程中，当出现字符不相等时，只需将模式串向右滑动2个字符，从i=2、j=0开始比较即可。在整个KMP算法中，主串中的i指针没有回退。

下面来讨论一般情况。设主串S=“s0s1s2...sn-1”模式串T=“t0t1t2...tm-1”。在模式匹配过程中，若出现字符不匹配的情况，即当si≠tj（0≤i<n，0≤j<m），有：

"si-j si-j+1 ... si-1"="tj-k tj-k+1 ... tj-1"（1）

即说明至少在字符si之前有一部分字符是相等的。

若子串（即模式串）中存在收尾重叠的真子串，即：

"t0 t1 ... tk-1" = "tj-k tj-k+1 ... tk-1"（2）

根据（1）（2）可以得出：

"si-k si-k+1 ... si-1" = "t0 t1 ...tk-1"

如图



因此，在匹配的过程中，主串中的第i个字符与模式串的第j个字符不等时，仅需将子串向右滑动，使si与tk对齐，接着进行后续的比较，此时，模式串中的子串"t0 t1 ... tk-1" 必与主串中的子串"si-k si-k+1 ... si-1" 相等。

如图



【求next函数值】

下面就来确定模式串需要滑动的具体位置。令next[j]=k，则next[j]表示当模式串中的第j个字符与主串中对应的字符不相等时，需要重新与主串比较的模式串字符位置，也就是需要将模式串滑动到第几个字符与主串比较。

求模式串中的next函数定义如下图：



其中，第1种情况，next[j]的函数是为了方便算法设计而定义的；

第2种情况，如果子串（模式串）中存在首尾重叠的真子串，则next[j]的值就是k，即模式串的最长子串的长度；

第3种情况，如果模式串中不存在重叠的子串，则从子串的第一个字符开始比较。

由此可以得到模式串“abcac”的next函数值

如图



KMP算法的模式匹配过程：如果模式串T中存在真子串"t0 t1 ... tk-1" = "tj-k tj-k+1 ... tj-1"，当模式串T的tj与主串的si不相等，按照next[j]=k将模式串向右滑动，从主串中的si与模式串的tk开始比较。如果si=tk，则继续比较下一字符。如果si≠tk，则按照next[next[j]]将模式串继续向右滑动，将主串中的si与模式串中的next[next[j]]字符进行比较。如仍然不相等，则按照以上方法，将模式串继续向右滑动，直到next[j]=-1为止。这时，模式串不再向右滑动，从si+1开始与t0进行比较。



利用next函数值的一个模式匹配例子

如图



KMP模式匹配算法是建立在模式串的next函数值已知的基础上的。下面讨论如何求模式串的next函数值。

从上面的分析可以看出，模式串的next函数值的取值与主串无关，仅与模式串相关。根据模式串next函数定义，next函数可以由地推的方法得到。

设next[j]=k，表示在模式串T中存在以下关系：

"t0 t1 ... tk-1" = "tj-k tj-k+1 ... tj-1"

其中，0<k<j，k为满足等式的最大值，即不可能存在k'>k满足以上等式。计算next[j+1]的值需要考虑以下两种情况：

（1）若tj=tk，则表示在模式串T中满足以下关系：

"t0 t1 ... tk" = "tj-k tj-k+1 ... tj"

并且不可能存在k'>k满足以上等式。因此有

next[j+1]=k+1，即next[j+1]=next[j]+1

（2）若tj≠tk，则表示模式串T中满足以下关系：

"t0 t1 ... tk" ≠ "tj-k tj-k+1 ... tj"

此时，已经有"t0 t1 ... tk-1" = "tj-k tj-k+1 ... tj-1"，但是tj≠tk，把模式串T向右滑动到k'=next[k]（0<k<k'<j），如果有tj=tk'，则表示模式串中有"t0 t1 ... tk' " = "tj-k tj-k+1 ... tj"

因此得到

next[j+1]=k'+1 即next[j+1]=next[k']+1

如果tj≠tk' ，则将模式串继续向右移动到next[k']个字符与tj比较。如果仍不相等，则将模式串继续向右滑动到下标为next[next[k']]字符与tj进行比较。依此类推，直到tj和模式串中某个字符相等或者不存在任何k'满足"t0 t1 ... tk' " = "tj-k tj-k+1 ... tj"，则有

next[j+1]=0

上述讨论的是根据next函数的定义如何得到next函数值的方法。例如，模式串为T="abcdabcdabe"的next函数值

如图

 



例如，在已经得到的前3个字符next函数值的基础上，如果求next[3]。因为next[2]=1，且t2=t0，则next[3]=next[2]+1=2。接着求next[4]，因为t2=t0，但“t2t3”≠“t0t1”，所以需要将t3与下标为next[1]=0的字符即t0进行比较，因为t0≠t3，所以next[4]=1。