拓展KMP模板

拓展kmp可以求出最长公共前缀，数组extend【i】表示从i开始匹配的公共前缀长度。代码如下：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

const int n = 10050;
int next[n];
int extend[n];
string S;
string T;

void GetNext()
{
    int k = 0;
    int Tlen = T.length();
    next[0] = Tlen;
    while(k < Tlen - 1 && T[k] == T[k + 1])
        k++;
    next[1] = k;
    k = 1;
    for(int i = 2; i < Tlen; i++)
    {
        int p = k + next[k] - 1, L = next[i - k];
        if(i + L - 1 >= p)
        {
            int j = (p - i + 1) > 0 ? p - i + 1 : 0;
            while(i + j < Tlen && T[i + j] == T[j])
                j++;
            next[i] = j;
            k = i;
        }
        else next[i] = L;
    }
}

void GetExtend()
{
    int k = 0;
    int Slen = S.length();
    int Tlen = T.length();
    int MinLen = Slen < Tlen ? Slen : Tlen;
    while(k < MinLen && S[k] == T[k])
        k++;
    extend[0] = k;
    k = 0;
    for(int i = 1; i < Slen; i++)
    {
        int p = k + extend[k] - 1, L = next[i - k];
        if(i + L - 1 >= p)
        {
            int j = (p - i + 1) > 0 ? p - i + 1 : 0;
            while(i + j < Slen && j < Tlen && S[i + j] == T[j])
                j++;
            extend[i] = j;
            k = i;
        }
        else extend[i] = L;
    }
}

int main()
{
    
}