简介

给定长度为n的文本串S和长度为m的模式串T，定义extend[i]为S[i…n-1]与T[0…m-1]的最长公共前缀长度，求extend[i]。当extend[x]==m时，则可知文本串S中包含模式串T，并且首位置为x，而这正是KMP算法处理的模式匹配问题。相较于KMP算法，扩展KMP算法能找到文本串S中所有模式串T的匹配，更一般地，可以知道文本串S中以每个字符开始的后缀与模式串T的最长公共前缀长度，时间复杂度O(n+m)。

扩展KMP

假设遍历到i时，已经求出extend[0…i-1]的值。我们记录下遍历过程中匹配成功的字符的最远位置为p，并且这次匹配的起始位置为a。换句话说，计算到x时，匹配成功的最远位置是x+extend[x]-1，p就是x=0…i-1得到的最大值，a就是对应的x。

设辅助数组next[i]表示T[i…m-1]和T[0…m-1]的最长公共前缀长度（注意这里与KMP算法中的next数组含义不同）。令len=next[i-a]，讨论以下两种情况：

(1) i + len-1 < p

小于

由next数组定义可知 T[0…len-1] == T[i-a…i-a+len-1]，并且由extend数组定义可知 S[a…p] == T[0…p-a]，得到 S[i…i+len-1] == T[i-a…i-a+len-1] ，所以 S[i…i+len-1] == T[0…len-1]。并且 S[i+len-1…p] != T[len-1…i-a]，不然违背了next数组最长公共前缀长度的定义。于是，无需任何比较就可以得出extend[i] = len。

(2) i + len-1 >= p

大于

我们可以看到，匹配最远的位置只到p，对于p之后的匹配结果是未知的，所以我们需要继续匹配S[p…n-1]和T[p-i…m-1]。匹配完之后，还需要更新a和p。

以上就是扩展KMP的主要思想，遍历即可，下面给出字符串下标从0开始的一种exKMP的实现，注意为了实现方便，代码中的p是上面分析的p+1，所以判断的时候是i+next[i-a]。而且同时用了变量j跟踪p在文本串S与模式串T中的对应位置，注意遍历文本串S时，i在递增，j需要递减。

 1void exKMP(char* s, char* t, int n, int m)
 2{
 3    int a, p;
 4    for (int i=0, j=-1; i<n; i++, j--)  //j即等于p与i的距离，其作用是判断i是否大于p（如果j<0，则i大于p）
 5    {
 6        if (j<0 || i+nxt[i-a] >= p)
 7        {
 8            if (j<0) p = i, j = 0;      //如果i大于p
 9            while (p<n && j<m && s[p]==t[j]) p++, j++;
10            extend[i] = j, a = i;
11        } else
12            extend[i] = nxt[i-a];
13    }
14}

next数组

根据next数组定义，next[i]表示T[i…n]和T[0…n]的最长公共前缀的长度，其实就相当于模式串T与自身的匹配，不过这里next数组是从1开始的，next[0]匹配的肯定是整个串的长度m。有兴趣的可以试试写到一个函数中去，下面模板中给出分离的实现。再次强调C++中next是关键字（迭代器的一个函数），可以换个名字避免 CE。

模板

 1char s[mxn], t[mxn];
 2int nxt[mxn], extend[mxn];
 3
 4void getnxt(char* t, int m)
 5{
 6    int a, p; nxt[0] = m;
 7    for (int i=1, j=-1; i<m; i++, j--)
 8    {
 9        if (j<0 || i+nxt[i-a] >= p)
10        {
11            if (j<0) p = i, j = 0;
12            while (p<m && t[p]==t[j]) p++, j++;
13            nxt[i] = j, a = i;
14        } else
15            nxt[i] = nxt[i-a];
16    }
17}
18
19void exKMP(char* s, char* t, int n, int m)
20{
21    int a, p;
22    for (int i=0, j=-1; i<n; i++, j--)  //j即等于p与i的距离，其作用是判断i是否大于p（如果j<0，则i大于p）
23    {
24        if (j<0 || i+nxt[i-a] >= p)
25        {
26            if (j<0) p = i, j = 0;      //如果i大于p
27            while (p<n && j<m && s[p]==t[j]) p++, j++;
28            extend[i] = j, a = i;
29        } else
30            extend[i] = nxt[i-a];
31    }
32}
33
34
35int main()
36{
37    scanf("%s%s", s, t);
38    getnxt(t, strlen(t));
39    exKMP(s, t, strlen(s), strlen(t));
40
41    for(int i=0; i<strlen(t); i++)
42        printf("%d ", nxt[i]);
43    printf("\n");
44
45    for(int i=0; i<strlen(s); i++)
46        printf("%d ", extend[i]);
47    printf("\n");
48
49    return 0;
50}