你说得对，但是随机化

NATO · 2024-06-29 11:59:26 · 题解

余于甲辰年，庚午癸亥闻此，叹于随机化之巧，故作此篇，以告其巧之于诸公也。

思路浅析：

题目中所谓的旋转操作的形式化定义：

有一个字符串 s_1s_2s_3...s_n，旋转一次之后即变为 s_2s_3...s_ns_1，即循环位移 1 位。

在不考虑翻转操作时，题意即是求两个字符串最长循环同构串的长度。

考虑翻转操作翻两次就与原串无异，故只需要考虑将某一个串翻转后和两个都不翻转得到的答案即可。

那么两个循环同构的串有神马性质呢？

考虑我循环位移多次后，将串以现在的 s_n 和 s_1 的位置分离开，我们发现前面的部分即为原串的一个后缀，后面的部分即为原串的一个前缀，可以发现对于一个循环位移了任意次的字符串与原串比较均有此结论，即两个串循环同构当且仅当第一个串的某个前缀是第二个串的后缀，两个串的剩余部分相同。

同时，我们发现我们让上文所述的前缀尽可能长是不劣的，考虑我第一个串的那个是第二个串的后缀的前缀向后扩展一位，那么最坏情况下也只是两个串的剩余部分减小一位：

（红色和黄色部分即为最长循环同构串）

可以发现，答案是不会因此变差的。

（下约定 s_i 表示第一个串的第 i 个字符，t_j 表示第二个串的第 j 个字符，并认为两个字符串长度均为 n。）

那么一个 O(n^3) 的做法便轻松出台了：

枚举两个对应字符相同的 s_i,t_j，以它们为公共子串的一部分向左向右将这个公共子串尽可能地扩展开，再在一头扩展 s 中循环子串的部分，反方向对应扩展 t 中循环子串的部分，使用字符串哈希判断扩展部分的两者是否相同即可。

考虑优化，我们知道一个期望时间复杂度 O(n^2) 的找最长公共子串的方法，即不断地随机两个位置 i,j，若 s_i=t_j，则向左向右尽力扩展这个公共子串到不能扩展为止，取这样扩展的最大值为答案即可。它为什么是 O(n^2) 的呢？考虑设最长公共子串长度为 l，则我有 \frac{l}{n} 的概率在 s 中随机到最长公共子串中的某个位置，以 \frac{1}{n} 的概率在 t 中随机到对应的位置，而单次扩展显然是不超过 l 次的，故期望复杂度为 O(n^2)。

套用上述做法，随机枚举的 s_i,t_j，同样扩展公共子串，不过在扩展剩余部分时钦定其长度不超过扩展的公共子串长度即可，可以证明期望复杂度是 O(n^2) 的（设答案长度为 l，而“钦定其长度不超过扩展的公共子串长度”就保证了扩展剩余部分的次数不会超过上述证法中的公共子串长度的，最多多一个常数 2，再套用上述证法，将 \frac{l}{n} 换为 \frac{l}{2n}，可以发现不过是多了一个常数 4 罢了）。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define un unsigned
using namespace std;
const ll MAXN=2;
ll MODs[MAXN+1];
random_device seed;
unsigned ll hss[MAXN+1][3005],hst[MAXN+1][3005];
unsigned ll bs[MAXN+1][200010];
const un ll base=19260817;
char s[3005],t[3005];
ll ans,sst,tst;
un ll get_hss(ll uid,ll l,ll r)
{
    return ((hss[uid][r]-hss[uid][l-1]*bs[uid][r-l+1]%MODs[uid])+MODs[uid])%MODs[uid];
}
un ll get_hst(ll uid,ll l,ll r)
{
    return ((hst[uid][r]-hst[uid][l-1]*bs[uid][r-l+1]%MODs[uid])+MODs[uid])%MODs[uid];
}
bool check(ll sl,ll sr,ll tl,ll tr)
{
    for(ll i=1;i<=MAXN;++i)if(get_hss(i,sl,sr)!=get_hst(i,tl,tr))return 0;
    return 1;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    mt19937 rd(seed());
    cin>>s>>t;
    clock_t st=clock();
    ll n=strlen(s),m=strlen(t);
    MODs[1]=1000000007ll;MODs[2]=998244353ll;
    for(ll k=1;k<=MAXN;++k)
    {
        bs[k][0]=1; 
        for(ll i=1;i<=max(n,m);++i)
        bs[k][i]=bs[k][i-1]*base%MODs[k];
    }
    for(ll k=1;k<=MAXN;++k)
    for(ll i=1;i<=n;++i)
    hss[k][i]=(hss[k][i-1]*base+s[i-1]-'a'+1)%MODs[k];  
    for(ll k=1;k<=MAXN;++k)
    for(ll i=1;i<=m;++i)
    hst[k][i]=(hst[k][i-1]*base+t[i-1]-'a'+1)%MODs[k];
    while((clock()-st)*1000.00/CLOCKS_PER_SEC<=700) 
    {
        ll sl=rd()%n+1,tl=rd()%m+1;
        if(s[sl-1]!=t[tl-1])continue;
        ll lenr=1;
        for(;sl+lenr<=n&&tl+lenr<=m&&s[sl+lenr-1]==t[tl+lenr-1];++lenr);
        while(sl-1>=0&&tl-1>=0&&s[sl-2]==t[tl-2])--sl,--tl,++lenr;
        ll maxl=0;
        ll sr=sl+lenr-1,tr=tl+lenr-1;
        for(ll lenl=1;(sl-lenl)&&tr+lenl<=m&&lenl<=lenr;++lenl)
            if(check(sl-lenl,sl-1,tr+1,tr+lenl))
            maxl=lenl;
        if(maxl+lenr>ans)
        {
            ans=maxl+lenr;
            sst=sl-maxl;tst=tl;
        }
        maxl=0;
        for(ll lenl=1;(tl-lenl)&&sr+lenl<=n&&lenl<=lenr;++lenl)
            if(check(sr+1,sr+lenl,tl-lenl,tl-1))
            maxl=lenl;
        if(maxl+lenr>ans)
        {
            ans=maxl+lenr;
            sst=sl;tst=tl-maxl;
        }
    }
    reverse(t,t+m);
    for(ll k=1;k<=MAXN;++k)
    for(ll i=1;i<=m;++i)
    hst[k][i]=(hst[k][i-1]*base+t[i-1]-'a'+1)%MODs[k];
    while((clock()-st)*1000.00/CLOCKS_PER_SEC<=1400)    
    {
        ll sl=rd()%n+1,tl=rd()%m+1;
        if(s[sl-1]!=t[tl-1])continue;
        ll lenr=1;
        for(;sl+lenr<=n&&tl+lenr<=m&&s[sl+lenr-1]==t[tl+lenr-1];++lenr);
        while(sl-1>=0&&tl-1>=0&&s[sl-2]==t[tl-2])--sl,--tl,++lenr;
        ll maxl=0;
        ll sr=sl+lenr-1,tr=tl+lenr-1;
        for(ll lenl=1;(sl-lenl)&&tr+lenl<=m&&lenl<=lenr;++lenl)
            if(check(sl-lenl,sl-1,tr+1,tr+lenl))
            maxl=lenl;
        if(maxl+lenr>ans)
        {
            ans=maxl+lenr;
            sst=sl-maxl;tst=m+1-(tl+ans-1);
        }
        maxl=0;
        for(ll lenl=1;(tl-lenl)&&sr+lenl<=n&&lenl<=lenr;++lenl)
            if(check(sr+1,sr+lenl,tl-lenl,tl-1))
            maxl=lenl;
        if(maxl+lenr>ans)
        {
            ans=maxl+lenr;
            sst=sl;tst=m+1-(tl-maxl+ans-1);
        }
    }
    cout<<ans<<'\n'<<sst-1<<' '<<tst-1;
}