题解 | 不是烤串故事

这道题好难喵！

给猫猫做傻了喵！

借用了蒟蒻果冻01大佬的O(n) 思想，仅仅只是为了让更多人和猫猫一样理解他的思想喵！

猫猫解释时间到！(≧▽≦)

第一步：看看 t 的开头有几个相同的小可爱

设定一个 z 来统计 t 开头有多少个连续相同的字符

int z = 1;
while (z + 1 < n && t[z] == t[z + 1]) ++z;

就像在数一群小猫咪，看看它们是不是都穿着同样的衣服。比如 t = "aaab"，前三个都是 'a'，所以 z = 3。这个信息后面有大用处喵！

第二步：从尾巴开始，数一数 s 和 t 有多少连续相同的位置

也就是数组b的含义啦!

b [ i ]的值代表从 i 开始往后有多少个s所在位和t所在位连续相同的字符数。

for (int i = n - 1; i >= 0; --i) {
    if (s[i] == t[i]) b[i] = 1 + b[i+1];
    else b[i] = 0;
}

从右往左看，如果当前位置两个字符一样，就记下从这往右有多少个连续一样的。

这样后面如果整个反转部分都匹配上了，就能直接加上这些后续的匹配长度啦！

第三步：递推 a[i] —— 最核心的一步！

a [ i ]的值代表从0到i翻转后，在“翻转范围内”从前往后可以和t匹配的最大长度。注意不是题目中的lcp啦！

if (s[i] != t[0]) { a[i] = 0; continue; }

反转后的第一个字符是 s[i]，如果它和 t[0] 不一样，那直接没戏，a[i] = 0。

否则，我们看看前一个状态 a[i-1] 是多少，记作 x。

现在有两种情况：

• 如果 x 比 z 还大：说明之前匹配的长度已经超过了 t 开头重复段的长度
• 那么a[i]就直接等于z。
• 举个例子喵！
• 假如a[4]所在的反转范围内的s为abaa翻转过来是aaba，假设t为aaba。那么此时a[4]是4大于z（2）。
• 在a[5]时所在的s一定是abaaa，翻转过来时aaaba原本的第三位的a必定和b（即第z+1位的不同值冲突）
• 故而a[i]一定等于z。
• 如果 x 小于等于 z ：说明 x 没有超过重复段，我们可以尝试继续向后匹配。
• 从 p = x+1 开始，比较 t[p] 和 s[i-p]（因为反转后第 p 个字符来自原串的 i-p 位置）。一直比到不匹配或者超过 i 为止，a[i] 就等于这个 p。
• 为什么要从x+1开始呢？
• 之前已经判断了s[i]和t[0]一样了且之前匹配的数(x)比z小，即全是t[0]。那么一定0到x是匹配的喵！

第四步：组合成真正的 LCP

int now = a[i];
if (now == i + 1) {
    if (i + 1 < n) now += b[i + 1];
}

如果整个反转部分都匹配了（now == i+1），那么后面可能还能接上原串剩余部分的匹配，而 b[i+1] 正好告诉我们后面能接多长。这样 now 就是真正的 LCP 长度啦！

第五步：找最大值和最小下标

遍历所有 i，记录最大的 now 和最先出现的 i，然后输出（记得 i 要加 1 哦）。

接下来就是代码展示了，代码的注释更清晰喵！

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

void solve()
{
    int n;cin >> n;//字符串长度
    string s,t;cin >> s >> t;//两个字符串

    int z=1;//统计t开头有多少个连续相同的字符
    while(z+1<n&&t[z]==t[z+1]) z++;

    vector<int> a(n,0);//代表从0到i翻转后，
    //在“翻转范围内”从前往后可以和t匹配的最大长度
    //注意不是题中的lcp

    vector<int> b(n,0);//从i开始往后有多少个“连续”相等的字符数

    //初始化b
    for(int i=n-1;i>=0;i--)
    {
        if(s[i]==t[i])
        {
            b[i]=1;//只要该位相等就至少有个1
            if(i+1<n) b[i]+=b[i+1];//继承后一位的
        }
        else b[i]=0;
    }

    //初始化a
    if(s[0]==t[0]) a[0]=1;//初始情况
    
    for(int i=1;i<n;i++)
    {
        //从0到i翻转
        if(s[i]!=t[0]) //如果是s[i]不等于t[0]
            continue;//那么反转后的第一个字符就不匹配，直接跳
        int x=a[i-1];//继承
        //x意为翻转0到i-1时反转部分与t的匹配长度
        
        if(z<x)
        {
            //之前匹配的长度超过了z（t的前缀重复段）
            //新匹配最多只能到重复段末尾
            a[i]=z;
        }
        else 
        {
            //之前已经判断了s[i]和t[0]一样了
            //且之前匹配的数(x)比z小，即全是t[0]
            //那么一定0到x是匹配的
            int p=x+1;
            //进行剩下的匹配
            while(p<=i&&t[p]==s[i-p]) p++;
            a[i]=p;//得到匹配的值
        }
    }

    int mx=0,best_i=-1;
    for(int i=0;i<n;i++)
    {
        int now=a[i];//翻转范围内匹配的数量

        if(now==i+1)//如果翻转范围内全匹配了
        {
            if(i+1<n) now+=b[i+1];//接上后面的
        }
        if(now>mx)//如果比mx大就更新
        {
            mx=now;
            best_i=i;
        }
    }

    if(mx==0) cout << "0 1\n";
    else cout << mx << ' ' << best_i+1 << '\n';
    //注意题中索引是从1开始的
    
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;cin >> t;
    while(t--) solve();
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/