Z函数（扩展kmp）模版

定义

对于一个长度为n的字符串 ，定义函数z[i]表示s和s[i,n-1]（即以s[i]开头的后缀）的最长公共前缀（LCP）的长度，则z被称为s的 Z 函数。特别地,z[0]=0。

思路

整体上类似dp，用之前算好的状态推导目前的状态，算法复杂度为O(n);具体细节推荐看一下Oi-wiki

应用

匹配子串

模版

牛客周赛round56 F

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include <sstream>
#include<map>
using namespace std;
//#define int long long
//#define ll long long
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int T;
int n;
int dp[N];
int lca[N];
string s, t, m;
int z[2 * N+1];
//关键函数
void z_function(string s) {
    int n = (int)s.length();
    memset(z, 0, sizeof(z));
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r && z[i - l] < r - i + 1) {
            z[i] = z[i - l];
        }
        else {
            z[i] = max(0, r - i + 1);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]])++z[i];
        }
        if (i + z[i] - 1 > r)l = i, r = i + z[i] - 1;
    }
    return;
}
signed main() {
    cin >> T;
    while (T--) {
        //初始化
        memset(dp, 0, sizeof(dp));
        s = ""; t = ""; m = "";
        //读入 n,s,t
        cin >> n >> s >> t;
        //顺序前缀
        for (int i = n-1; i >=0; i--) {
            if (s[i] == t[i])dp[i] = 1 + dp[i + 1];
        }
        //m=t+翻转s   (0,n-1)+(n,2n-1)
        reverse(s.begin(), s.end());
        m = t + "" + s;
        //逆序前缀
        z_function(m);int k=1, maxx = 0;
        for (int i = 0; i < n; i++) {
            if (z[2 * n - 1 - i] < i + 1) {
                lca[i] = z[2 * n - 1 - i];
            }
            else {
                lca[i] = z[2 * n - 1 - i] + dp[i + 1];
            }
            //寻找最长前缀以及最小翻转下标
            if (maxx < lca[i]) {
                maxx = lca[i];
                k = i + 1;
            }
        }
        cout << maxx << " " << k << "\n";
    }
}