题解 | 不是烤串故事

这里直接利用z函数的信息复用思想，可以达到最优的时间复杂度.

发现可以先得到从每个开始的和的后缀的LCP的长度，记为数组 b.

难点是得到翻转后与的LCP的长度，记为数组 a：

​ 设已经得到，此时和的末尾分别加上一个和，如果，那么显然的；否则设与的LCP的长度为，如果，那么与的LCP的长度小于，也就是 $ t[2...i] $ 与翻转后的LCP的长度小于，可以直接得到；如果，那么还要检查一下与翻转后的LCP的长度，记为，于是$ a[i]=1+x+delta $。

​ 注意这里每次的总和不超过，所以时间复杂度为 $ O(n) $ .

​ 如果觉得上述解释不好懂，可以看下图。C++代码在图下面。

#include <bits/stdc++.h>
using namespace std;


int main() {
    int tt; cin >> tt;
    while (tt--) [&]()->void {
        int n; cin >> n;
        string s, t; cin >> s >> t;
        int z = 0;
        while (1 + z < n && t[z] == t[z + 1]) {
            ++z;
        }
        vector<int> a(n), b(n);
        for (int i = n - 1; i >= 0; --i) {
            b[i] = (s[i] == t[i] ? (1 + (i < n - 1 ? b[i + 1] : 0)) : 0);
        }
        a[0] = int(s[0] == t[0]);
        for (int i = 1; i < n; ++i) {
            if (s[i] != t[0]) {
                a[i] = 0;
            } else {
                int x = a[i - 1];
                if (z < x) {
                    a[i] = 1 + z;
                } else {
                    int p = 1 + x;
                    while (p <= i && t[p] == s[i - p]) {
                        ++p;
                    }
                    a[i] = p;
                }
            }
        }
        int mx = 0, p = -1;
        for (int i = 0; i < n; ++i) {
            int cur = a[i];
            if (cur >= i + 1) {
                cur += (i < n - 1 ? b[i + 1] : 0);
            }
            if (cur > mx) {
                mx = cur;
                p = i;
            }
        }
        if (mx == 0) {
            cout << "0 1\n";
        } else {
            cout << mx << ' ' << (p + 1) << '\n';
        }
    }() ;




    return 0;
}