KMP算法与优化（串的模式匹配）_设主串 s=“aabcbabcaabcaababc ”,模式 t=“abcaababc ”,求出该模

• 什么是串的模式匹配

模式匹配即子串定位操作Index(S,T,pos)，是串处理系统中最常见的操作(如查找)，从主串S第pos个位置开始查找与模式串T相等的子串

例子：主串S=“ababcabaabcac”，模式串T=“abaabcac”，从S的第1个位置开始查找与T相等的子串。

说明：本文所用数组的0号位用于存储串长度，故如：串S的第i位可用S[i]表示。

蛮力算法(Brute Force)/简单算法

算法思想:从主串第pos个字符起(i),//逐个字符与T中当前字符(j)比较，若相同则比较下一个(i++,j++),不同则i回溯到S中“下一个开始比较的地方”,重新比较//如此重复直到匹配成功(j>T[0])或者i越界(i>S[0])

说明:在第i个时失配如何将i后退到“下一个开始比较的地方”?
S到到目前已匹配了j-1个，故第一个匹配的位序是i-(j-1),故“下一个开始匹配的是i-j+2

求解例子过程

1. 第一次查找，从S的第1个位置开始
   比较到S的第4个位置时，发现不同，进入第二次查找。
   
2. 第二次查找，从S的第2个位置开始
   直接就不同，进入第三次查找。
   
3. 第三次查找，从S的第3个位置开始
   比较到S的第5个位置时，发现不同，进入第四次查找。
   
4. 第四次查找，从S的第4个位置开始
   直接就不同，进入第五次查找。
   
5. 第五次查找，从S的第5个位置开始
   直接就不同，进入第六次查找。
   
6. 第六次查找，从S的第6个位置开始，匹配成功。
   

通过这个例子我们发现，BF算法实际每次失配都将回溯从下个开始位置再比较，能否不回溯从而减少不必要的比较次数呢？

kmp算法就找到了方法，解决了回溯的问题。

kmp算法

我们先看上面蛮力算法求解例子的过程。通过第一次的查找，我们其实已经知道主串S的前面3位是什么了。要想在第二次查找时不回溯，那我们就需要考虑一个问题：我们应该让模式串T的哪个位与主串S当前位继续进行比较。这个问题我们要怎么求解呢？

假设此次查找比较到S[i]与T[j]不匹配了，然后选T[k]继续与S[i]进行比较。那就隐含着T的1到k-1位是与S的i-k+1到i-1位刚好匹配。
即：找到S中截止到S[i-1]的真右子串，它与T中T[1]开始的左子串相等且该子串尽量长，S[i]接下来应该比较的字符为T[子串长度+1]

i不回溯，当S[i]与T[j]失配时设法找到下一个与S[i]进行比较的T[k]即可。关键在于求k，实际k只与j相关,如何求k=next[j]？
下面给出next[j]的人工求解过程：

1. 若S[i]与T[1]不配，则S[i]不应再与T中元素比较，next[1]=0，i后移
2. 若S[i]与T[2]不配，只能再拿S[i]与T[1]比；故next[2]=1
3. 假设j>=3，如前所述，找S中截止到S[i-1]的真右子串，它与T中T[1]开始的左子串相等且该子串尽量长。next函数值为[子串长度+1]
4. j=3时, T中截止到T[3-1]为‘ab’，它只有一个真右子串’b’,因T[1]开始的子串以a开头,故找不到符合条件的子串，此时next[3]=0+1=1
5. j=4时, ‘aba’中截止到T[4-1]=‘a’的真子串{ba,a}中只有 ‘a’与T[1]开始的子串T[1…1]=’a’等，故next[4]=1+1=2;
6. j=5时, ‘abaa’中截止到T[5-1]=‘a’的真子串{baa,aa,a}中只有‘a’与T[1]开始的子串T[1.1]=’a’等，故next[4]=1+1=2;
7. j=6时, ‘abaab’中截止到T[6-1]=‘b’的真子串{baab, aab,ab,b}中只有’ab’与T[1…2]等，故next[6]=2+1=3;

kmp例子求解过程

1. 第一次查找，从S[1]和T[1]开始，到S[4]和T[4]失败，next[4]=2，令j=2。
   
2. 第二次查找，从S[4]和T[2]开始，到S[5]和T[3]失败，next[3]=1，令j=1。
   
3. 第三次查找，从S[5]和T[1]开始，直接失败，next[1]=0，令i++，j=1。
   
4. 第四次查找，从S[6]和T[1]开始，匹配成功。
   

kmp算法思想与实现

算法思想:从主串第pos个字符起(i)，逐个字符与T中当前字符(j)比较，若相同则比较下一个(i++，j++)，不同则令j=next[j]，重新比较S[i]与T[j]，如此重复直到匹配成功(j>T[0])或者i越界(i>S[0])

int Index_KMP(SString S, SString T, int pos) {
    int i = pos;
    int j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (S[i] == T[j] || j == 0 ) {
            ++i;
            ++j;
        } //匹配或next==0则后移
        else {
            j=next[j];
        } //特点：S的i指针不回溯,S[i]重新与T[j]比较
    }
    if (j > T[0]) return i-T[0]; //子串结束，说明匹配成功
    else return 0;
} //Index_KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

kmp算法优化

引例

主串为S=“aaabaaaab”，模式串T=“aaaab”。
按照kmp算法，先求next[j]如下：

查找过程如下：

1. 第一次查找，从S[1]和T[1]开始，到S[4]和T[4]失败，next[4]=3，令j=3。
   
2. 第二次查找，从S[4]和T[3]开始，到S[4]和T[3]失败，next[3]=2，令j=2。
   
3. 第三次查找，从S[4]和T[2]开始，到S[4]和T[2]失败，next[2]=1，令j=1。
   
4. 第四次查找，从S[4]和T[1]开始，到S[4]和T[1]失败，next[1]=0，令i++，j=1。
   
5. 第五次查找，从S[5]和T[1]开始，匹配成功。
   
   注意： 第一次S[4]与T[4]失配时，拿S[4]与T[3]比，因为此处T[4]==T[3]，S[4]没必要与T[3]进行比较，而应该直接和next[3]比较，即和next[next[4]]进行比较。故计算next函数时如出现:
   $$T[j]=T[next[j]]$$
   可作如下改进：
   $$next[j]=next[next[j]]$$

优化的kmp算法

针对引例求解如下：

1. 第一次查找，从S[1]和T[1]开始，到S[4]和T[4]失败，nextval[4]=0，令i++，j=1。
   
2. 第二次查找，从S[5]和T[1]开始，匹配成功。
   

模式匹配算法复杂度分析

• BF的最坏情况，S与T之间存在大量的部分匹配，比较总次数为$(S[0]-T[0]+1)\ast T[0]＝O(S[0]\ast T[0])$
• Next函数与nextval函数的求取：复杂度$O(T[0])$，且模式串一般很短
• KMP算法：由于指针i无须回溯，对主串仅需从头到尾扫描一遍，尤其适于处理从外设输入的庞大文件，因无需回头读，更何况有些存储设备如磁带不能随机回溯。此外，KMP算法比较次数有所降低，复杂度为$O(S[0]+T[0])$。注意子串指针每右移一次则主串指针也移

$next[j]$编程求解

递推法求next函数值

$已知：T[1]=0$;
$记i’=i-1，若next[i’]=j，T[1..j-1]==T[i’-j+1..i’-1]，下面求next[i]$

1. $若T[i’]==T[j]则说明T[1..k]==T[j-k+1..j],故next[i]=j+1$
2. $｛若T[i’]==T[j]则说明T[i’-j+1..i’]与T[1..j]只最后一个字符不匹配,如此应让T[i’]与T[next[j]]比较，或者说令j=next[j]，重复1、2步骤，直到T[i’]==T[j]或j==0。前者next[i]=j+1,后者next[i]=1$

void get_next(SString &T, int &next[]) {
    // 求模式串T的next函数值并存入数组next
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T[0]) {//共有T[0]个next值需要求取
        if (j == 0 || T[i] == T[j]) {
            //第一种情况或者第二种情况下j=0
            ++i;
            ++j;
            next[i] = j;
        }
        else j = next[j];//第二种情况下j变成next[j]
   }
 } // get_next 复杂度：O(T[0])

void get_nextval(SString &T, int &next[]) {
    // 求模式串T的nextval函数值并存入数组nextval
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < T[0]) {//共有T[0]个next值需要求取
        if (j == 0 || T[i] == T[j]) {//第一种情况或者第二种情况下j=0
            ++i;
            ++j;
            if (T[i] != T[j]) nextval[i] = j;
            else nextval[i] = nextval[j];
        }
        else j = nextval[j];//第二种情况下j编程next[j]
    }
 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30