不是烤串故事【牛客tracker 每日一题】
不是烤串故事
时间限制：2秒 空间限制：512M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小红有两个长度为n nn的字符串s ss和t tt，我们定义下标从1 11开始，现在你可以选取字符串s ss的前i ii个字符s 1 s 2 ⋯ s i s_1s_2⋯s_is1s2⋯si，然后将这一部分反转后与剩余部分拼接，得到s i ′ s_i^′si′。
请你找到每一个翻转前缀s i ′ s_i^′si′与字符串t tt的m a x _ l e n i = 1 n { l c p ( s i ′ , t ) } max\_len_{i=1}^n\{lcp(s_i^′,t)\}max_leni=1n{lcp(si′,t)}，即长度最长的l c p ( s i ′ , t ) lcp(s_i^′,t)lcp(si′,t)。在这里，l c p lcplcp代表最长公共前缀。
好吧，这其实并不难，作为神秘的F FF题，你同时需要输出满足上述条件的最小的i ii。
在本题中，反转即为将字符串绕中心字符前后反转，具体地说，设字符串为s 1 s 2 ⋯ s n − 1 s n s_1s_2⋯s_{n−1}s_ns1s2⋯sn−1sn，反转后得到s n s n − 1 ⋯ s 2 s 1 s_ns_{n−1}⋯s_2s_1snsn−1⋯s2s1。
输入描述：
每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≤ T ≤ 100 ) T (1≤T≤100)T(1≤T≤100)代表数据组数，每组测试数据描述如下：
第一行输入一个整数n ( 1 ≤ n ≤ 10 6 ) n(1≤n≤10^6)n(1≤n≤106)代表字符串长度。
第二行输入一个长度为n nn，且仅由小写字母构成的字符串s ss。
第三行输入一个长度为n nn，且仅由小写字母构成的字符串t tt。
除此之外，保证所有的n nn之和不超过10 6 10^6106。
输出描述：
对于每一组测试数据，在一行上输出两个整数，代表最长l c p lcplcp长度和在此条件下最小的i ii。
示例1
输入：
3 6 baabaa aabbbb 3 abc bac 2 ab cd输出：
4 3 3 2 0 1说明：
对于第一组测试数据，我们这样描述整个过程：
- 选择前缀长度为1 11翻转s 1 ′ = " b a a b a a " s_1^′="baabaa"s1′="baabaa"，l c p = 0 lcp=0lcp=0；
- 选择前缀长度为2 22翻转s 2 ′ = " a b a b a a " s_2^′="ababaa"s2′="ababaa"，l c p = 1 lcp=1lcp=1；
- 选择前缀长度为3 33翻转s 3 ′ = " a a b b a a " s_3^′="aabbaa"s3′="aabbaa"，l c p = 4 lcp=4lcp=4；
- 选择前缀长度为4 44翻转s 4 ′ = " b a a b a a " s_4^′="baabaa"s4′="baabaa"，l c p = 0 lcp=0lcp=0；
- 选择前缀长度为5 55翻转s 5 ′ = " a b a a b a " s_5^′="abaaba"s5′="abaaba"，l c p = 1 lcp=1lcp=1；
- 选择前缀长度为6 66翻转s 6 ′ = " a a b a a b " s_6^′="aabaab"s6′="aabaab"，l c p = 3 lcp=3lcp=3；
所以最长的公共前缀为4 44，与此同时最小的翻转下标为3 33。
解题思路
本题核心是通过KMP算法+预处理数组高效计算每个翻转前缀对应的最长公共前缀（ l c p ） （lcp）（lcp）：首先预处理suc数组，记录从位置i开始s与t的连续匹配长度（未翻转部分）；利用K M P KMPKMP算法对反转的s前缀与t做匹配，生成pre数组，记录每个翻转前缀长度i对应的匹配长度；遍历每个i ii时，若翻转前缀匹配长度≥ i ≥i≥i，总l c p lcplcp为匹配长度加suc[i+1]（剩余未翻转部分匹配长度），否则为pre[i]；最后维护最大l c p lcplcp值及对应的最小i ii。该方法通过K M P KMPKMP将字符串匹配复杂度降至O ( n ) O(n)O(n)，每组数据总时间复杂度O ( n ) O(n)O(n)，适配总n ≤ 1 e 6 n≤1e6n≤1e6的规模，精准计算每个i ii的l c p lcplcp并找到最优解。
总结
- 核心逻辑：用K M P KMPKMP预处理翻转前缀与t tt的匹配长度，结合
suc数组处理未翻转部分匹配，计算每个i ii对应的总l c p lcplcp。 - 关键操作：预处理
suc数组记录未翻转匹配长度，通过K M P KMPKMP生成pre数组记录翻转前缀匹配长度，遍历i ii计算总l c p lcplcp。 - 效率保障：K M P KMPKMP算法使字符串匹配线性化，整体时间复杂度O ( n ) O(n)O(n)每组，适配大数据量要求。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<int>>vt;typedefpair<int,int>pll;constll N=1e6+10;constll mod=1e4+7;constll INF=1e18;chars[N],p[N];intnxt[N],pre[N],suc[N];voidsolve(){memset(pre,0,sizeof(pre));intn;scanf("%d%s%s",&n,s+1,p+1);suc[n+1]=0;for(inti=n;i;i--)suc[i]=s[i]==p[i]?suc[i+1]+1:0;for(inti=2;i<=n;i++){intj=nxt[i-1];while(j&&p[i]!=p[j+1])j=nxt[j];nxt[i]=p[i]==p[j+1]?++j:0;}intcur=0;for(inti=n;i;i--){while(cur&&s[i]!=p[cur+1])cur=nxt[cur];if(s[i]==p[cur+1])++cur,pre[i+cur-1]=max(pre[i+cur-1],cur);if(i==1){intk=cur;while(k){pre[i+k-1]=max(pre[i+k-1],k);k=nxt[k];}}}intlcp=0,pos=1;for(inti=1;i<=n;i++){inttmp=pre[i];if(pre[i]>=i)tmp+=suc[i+1];if(tmp>lcp)lcp=tmp,pos=i;}printf("%d %d\n",lcp,pos);}intmain(){intT;scanf("%d",&T);while(T--)solve();return0;}