字符串匹配算法

朴素模式匹配算法

主串长度为n，模式串长度为m

朴素模式匹配算法：将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。

最多对比n-m+1个子串。

index(S,T):定位操作。若主串S中存在与串T值相同的子串，则返回它在主串中第一次出现的位置；否则函数值为0；

int Index(SString S,SString T){
    int i=1,n=StrLength(S),m=StrLength(T);
    SString sub;  //用于暂存子串
    while(i<=n-m+1){
      SubString(sub,S,i,m); //截取子串放入sub中
      if(StrCompare(sub,T)!=0)++i;
      else return i; //返回子串在主串中的位置
    }
    return 0;  //S中不存在与T相等的子串。
}

使用两个指针直接通过数组下标实现朴素模式匹配算法。

使用i指针指向主串S的字符，j指针指向模式串T的字符，比较两个指针指向的字符，从头开始比较，当两个字符相同时，两个指针同时向后移动一位。如果两个指针指向的字符不同，说明匹配失败，则主串指针i指向下一个子串的第一个位置，模式串j指向模式串的第一个位置。

即当匹配失败时，设置：

i = i-j+2；j=1；

i-j是让i回到当前匹配的子串的前一个位置，加2移动到下一个子串的起始位置。

若j>T.length,则当前子串匹配成功，返回当前子串第一个字符的位置return i-T.length

int Index(SString S,SString T){
    int i=1,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;
}

主串长度为n，模式串长度为m，朴素模式匹配最坏的情况下时间复杂度为O(mn)

image-udyg.png

这种情况下，每次都要检查到模式串的末尾才知道匹配失败。（注：很多时候，n>>m)

KMP算法

基于朴素匹配算法进行优化。

在朴素匹配中，每次匹配失败时，主串指针i都要回溯到下一个子串的第一个位置，模式串的指针都要回溯到模式串的开头。已经知道当i和j指向的字符不匹配时，它们前面的字符一定是匹配的，那么可以根据前面匹配的字符信息改进指针的回溯。

如果当前失配的位置之前的子串具有前缀与后缀相等的情况，那么主串的指针i就可以保持不变，直接将模式串移动到前缀与后缀相等的位置开始进行比较，而不必从起始位置开始比较。

image-ookg.png

此时字符失配，可以将模式串如下移动

image-krry.png

直接跳过前三个字符的比较，减少子串的比较次数。

字符串的前缀、后缀和部分匹配值

前缀指除了最后一个字符外，字符串所有的头部子串（严格说是真前缀），后缀是除了第一个字符外，字符串所有的尾部子串（真后缀）。字符串的部分匹配值是字符串所有相等的前缀与后缀中最长的子串长度。

KMP算法流程

假设现在文本串S匹配到 i 位置，模式串T匹配到 j 位置

  • 如果 j = -1，或者当前字符匹配成功（即S[i]=T[j])，都令i++，j++，继续匹配下一个字符；
  • 如果 j！=-1，且当前字符匹配失败（S[i]!=T[j]),则令i不变，j=next[j]。此举意味着失配时，模式串相对于文本串S向右移动了j-next[j]位。
    • 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置-失配字符对应的next值，且此值大于等于next数组

next数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如next[j]=k，代表 j 之前的字符串中有最大长度为k的相同前缀后缀。

也意味着在某个字符失配时，该字符对应的next值会告诉你下一步匹配时，模式串应该调到哪个位置(next[j])。如果next[j]等于0或-1，则跳到模式串的开头字符，若next值大于0，则跳到j之前的某个字符，而不是跳到开头，因为相同的前缀后缀表示，next[j]部分的前缀已经与上一次匹配的字符串的后缀相匹配，所以可以直接从next[j]开始比较。

KMP代码：

int KmpSearch(char* s, char* p)  
{  
    int i = 0;  
    int j = 0;  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
    while (i < sLen && j < pLen)  
    {  
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++  
        if (j == -1 || s[i] == p[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]  
            //next[j]即为j所对应的next值  
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

image-ybqf.png

例如当模式串的D与主串的空格不匹配时，D前面部分的子串存在相同的前缀和后缀AB，当然主串中前面的子串与模式串是匹配的，也有相同的前缀后缀AB，所以下一次匹配的时候就可以按住主串的 i 不动，直接从模式串的C开始比较，即跳过前缀AB。此时 j 需要向左移动四位(next[j]=2)，移动到C的位置。

next数组

  1. 寻找前缀后缀最长公共元素长度

对于P = p0 p1 ...pj-1 pj，寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj，那么在包含pj的模式串中有最大长度为k+1的相同前缀后缀。举个例子，如果给定的模式串为“abab”，那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示：

image-gpth.png

比如对于字符串aba来说，它有长度为1的相同前缀后缀a；而对于字符串abab来说，它有长度为2的相同前缀后缀ab（相同前缀后缀的长度为k + 1，k + 1 = 2）。

2.求next数组

  • next数组考虑的是除当前字符外的最长相同前缀后缀，所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后，只要稍作变形即可：将第①步骤中求得的值整体右移一位，然后初值赋为-1，如下表格所示：

image-hkia.png

比如对于aba来说，第3个字符a之前的字符串ab中有长度为0的相同前缀后缀，所以第3个字符a对应的next值为0；而对于abab来说，第4个字符b之前的字符串aba中有长度为1的相同前缀后缀a，所以第4个字符b对应的next值为1（相同前缀后缀的长度为k，k = 1）。

  • 根据next数组进行匹配

匹配失配，j = next [j]，模式串向右移动的位数为：j - next[j]。换言之，当模式串的后缀pj-k pj-k+1, ..., pj-1 跟文本串si-k si-k+1, ..., si-1匹配成功，但pj 跟si匹配失败时，因为next[j] = k，相当于在不包含pj的模式串中有最大长度为k 的相同前缀后缀，即p0 p1 ...pk-1 = pj-k pj-k+1...pj-1，故令j = next[j]，从而让模式串右移j - next[j] 位，使得模式串的前缀p0 p1, ..., pk-1对应着文本串 si-k si-k+1, ..., si-1，而后让pk 跟si 继续匹配。如下图所示：

失配时j移动到next[j]

举例说明寻找最长前缀后置

如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示：

image-utzm.png

即原模式串对应的各个前缀后缀的公共元素的最大长度表为：

image-vndi.png

根据最大长度表求next数组：已知适配时需要将j移动到next[j]，也就是模式串向右移动的位数为：已匹配的字符数-失配字符的上一位字符对应的最大长度值。

上文利用这个表和结论进行匹配时，我们发现，当匹配到一个字符失配时，其实没必要考虑当前失配的字符，更何况我们每次失配时，都是看的失配字符的上一位字符对应的最大长度值。如此，便引出了next 数组。

给定字符串“ABCDABD”，可求得它的next 数组如下：

image-ypup.png

其实就是最大长度表向右移动一位，然后初始值赋值为1.（当然，你也可以直接计算某个字符对应的next值，就是看这个字符之前的字符串中有多大长度的相同前缀后缀）

image-hbtx.png

通过代码递推计算next数组

  • 如果对于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于next[j] = k。
    • 此意味着什么呢？究其本质，next[j] = k 代表p[j] 之前的模式串子串中，有长度为k 的相同前缀和后缀。有了这个next 数组，在KMP匹配中，当模式串中j 处的字符失配时，下一步用next[j]处的字符继续跟文本串匹配，相当于模式串向右移动j - next[j] 位。
  • 下面的问题是：已知next [0, ..., j]，如何求出next [j + 1]呢？

相当于也是一个KMP模式匹配问题，把前缀看成是模式串

对于P的前j+1个序列字符：

  • 若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1；
  • 若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]，则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀"p0 p1, …, pk-1 pk"跟后缀“pj-k pj-k+1, …, pj-1 pj"相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么这个t+1 便是next[ j+1]的值，此相当于利用已经求得的next 数组（next [0, ..., k, ..., j]）进行P串前缀跟P串后缀的匹配。

那为何递归前缀索引k = next[k]，就能找到长度更短的相同前缀后缀呢？这又归根到next数组的含义。我们拿前缀 p0 pk-1 pk 去跟后缀pj-k pj-1 pj匹配，如果pk 跟pj 失配，下一步就是用p[next[k]] 去跟pj 继续匹配，如果p[ next[k] ]跟pj还是不匹配，则需要寻找长度更短的相同前缀后缀，即下一步用p[ next[ next[k] ] ]去跟pj匹配。此过程相当于模式串的自我匹配，所以不断的递归k = next[k]，直到要么找到长度更短的相同前缀后缀，要么没有长度更短的相同前缀后缀。如下图所示：

image-hoha.png

求next数组代码如下“

void GetNext(char* p,int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀  
        if (k == -1 || p[j] == p[k])   
        {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else   
        {  
            k = next[k];  
        }  
    }  
}

但是这个next数组存在一点缺陷，比如模式串aaaab与主串aaabaaaab，当i=j=4时失配时，那么还需要进行s4与p3、s4与p2、s4与p1进行比较，由于p1=p2=p3=p4，那么后续的比较也必然会失配，这些比较完全是不必要的。

那么当p[j]=p[next[j]]时需要再次递归，将next[j]修改为next[next[j]]，直至两者不相等为止，更新后的数组命名为nextval。计算代码如下：

//优化过后的next 数组求法  
void GetNextval(char* p, int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀  
        if (k == -1 || p[j] == p[k])  
        {  
            ++j;  
            ++k;  
            //较之前next数组求法，改动在下面4行  
            if (p[j] != p[k])  
                next[j] = k;   //之前只有这一行  
            else  
                //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]  
                next[j] = next[k];  
        }  
        else  
        {  
            k = next[k];  
        }  
    }  
}