扩展KMP（exkmp）

扩展KMP

该算法旨在解决的核心问题是：针对输入的主串 S 和给定的模式串 T ，计算并确定其所有后缀与模式串 T 的最长公共前缀的长度。

该算法旨在通过主串S与模式串T之间的匹配来确定其出现频率及具体位置。而扩展型KMP算法则在此基础上增加了更多功能与应用场景。

exkmp 算法求解过程实际是求两个数组的值：

next[i] : 字符串 T 的后缀 Tsuf(i) 与其自身的最长公共前缀 （在 C++11 中 next 是保留字）

extend[i] ：主串 S 的后缀 Ssuf(i) 与模式串 T 的最长公共前缀长度

exkmp算法基于 递推计算 ，其中extend[i]的值能够通过extend[0..i]和net数组的数值进行计算得到。

算法推导：

令基准字符串 S 长度为 N, 目标模式 T 长度为 M, 索引从零开始。
当前正致力于计算 extend[k] 的值, 已知 extend[0..i] 和 net 数组已预知。

令最远匹配的位置为p（其中主串S的下标从0至K+1开始与模式串T每次以初始下标0进行匹配所能达到的最大主串S的位置），则满足条件的最大值p = \max(i + \text{extend}[i] - 1) ，其中i\in[0, k-1]（这里\text{extend}[i]表示第i个字符之后能够扩展的最大长度）。（即：\text{extend}[i]对应的是当前字符之后能够连续匹配的有效长度）

设 j 为 max 取得最大值的下标，即

p = j + extend[j] - 1

根据 extend[j] 的含义得到：

S[j..p] = T[0..p-j]

(p\geq k) 时 上式两边同时删去 [j..k-1] 得到：

S[k..p] = T[k - j..p - j] . . . . . . . . (1)

设 l = net[k-j] ，根据 net 数组的定义有：

T[0..l-1] = T[k - j..k - j + l - 1] . . . . . . . . (2)

是 net[k-j] 的原因是 (1) 式中 T 的下标是从 k-j 开始的。

-Case 1:
若 p - j > k - j + l - 1（ (1) 式 T 右端下标 > (2) 式 T 右端下标 ），
即 p > k + l -1 时 结合 (1)、(2) 式有：

S[k..k + l - 1] = T[k - j..k - j + l -1] = T[0..l - 1]

所以此时 extend[k] = l

-Case 2:
若 p - j \leq k - j + l - 1（ (1) 式 T 右端下标 \leq (2) 式 T 右端下标 ），
即 p \leq k + l -1 时 结合 (1)、(2)式有：

S[k..p] = T[0..p - k]

而在此时，在主串的位置p+1处开始就不再明确。 当主串中的位置在p+1时，在模式串中对应的位置是p−k+1处开始进行匹配。 其中 extend[k] 的计算结果等于基础长度l与额外增加的部分之和。
随后更新j和p的值。
因为最远匹配位置明显超过了当前的$j位置。

在上述算法推导过程中有一个重要前提是主串S与模式串T之间必须满足某种对应关系。当不满足上述小前提时（即当p < k时不等式不成立），必然满足另一个条件即p ≤ k + l -1。因此可将其归入Case 2处理。此时匹配的起始位置为：主串S从索引k的位置开始与模式串T进行比较

求解 net 数组：即该数组相当于其中以 T 为主串的特殊形式（特殊 exkmp），因此可采用前述方法进行计算。在上述算法中将 extend[i] 替代为 net[i] 即可。

考虑到 涉及到 net[k - j] 且 k-j \leq k 的情况出现时（当且仅当 j=0 且 k=1 时）会出现等式成立的情形），因此建议直接计算 net[1] 的值即可完成问题解决。

求解 net 数组的代码：

    void getNet(string& t){
    int len = t.length(),j=0,p,l;
    net[0] = len;
    while(j<len&&t[1+j]==t[j]) j++; //求 net[1]
    net[1] = j;
    j = 1;
    for(int k=2;k<len;k++){
        p=j+net[j]-1;l=net[k-j];
        if(p<=k+l-1){ // Case 2
            int i=p>=k?p-k+1:0; //p是否大于等于k，i为从k开始的匹配长度
            while(k+i<len&&t[k+i]==t[i]) i++;
            net[k]=i;
            j=k; //更新j
        }
        else net[k]=l; // Case 1
    }
    }
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    
    代码解释

求 extend 数组的代码：

    void getExtend(string& s,string& t){
    int ls = s.length(),lt =t .length(),j=0,p,l;
    while(j<ls&&j<lt&&s[j]==t[j]) j++; //求 extend[0]
    extend[0] = j;
    j = 0;
    for(int k=1;k<ls;k++){
        p=j+extend[j]-1;l=net[k-j];
        if(p<=k+l-1){ // Case 2
            int i=p>=k?p-k+1:0; //p是否大于等于k，i为从k开始的匹配长度
            while(k+i<ls&&i<lt&&s[k+i]==t[i]) i++;
            extend[k]=i;
            j=k; //更新j
        }
        else extend[k]=l; // Case 1
    }
    }
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    
    代码解释