题解：CF2053G Naive String Splits

· · 题解

先不考虑复杂度，就给你两个串，如何判定是否可以拼出 t 呢？

我们考虑如何正确地直接贪心。假设 \bm{s_1,s_2} 不存在公共循环节，原因后面再说。具体地，设我们试图用字符串 s_1,s_2 拼出字符串 t，且 \lvert s_1\rvert\le \lvert s_2\rvert。此处给定一个贪心：不断地匹配短串 s_1，直到匹配不上为止，然后尝试匹配一次 s_2。注意到这样可能会出问题，因为如果 s_2 有若干个 s_1 作为前缀，可能有类似反悔的操作。例如 s_1=\tt{ab}，s_2=\tt{ababc}。贪心匹配 t=\tt{abababc} 时，先用 s_1 匹配了 3 次，然后直接塞 s_2 也不合法，但是由于 s_2 包含两次 s_1 作为前缀，可以撤销掉这两个匹配重新尝试塞 s_2。

形式化地，设 s_2=s_1^k+c，我们每次先贪心匹配 s_1，然后遇到匹配不了的地方先直接匹配 s_2。如果失败了就撤回 k 次 s_1 的匹配，然后接着匹配 s_2。如果再失败，其实如果 c 是 s_1 的前缀，可以再撤回一次 s_1 并尝试匹配，具体可以手玩下面这个数据中 s_1=\tt{aba},s_2=\tt{abaab} 的情况：

1
8
abaabaab
abaababa

这个例子里，先匹配了两次 \tt{aba}，然后撤回发现 \tt{ababa}\neq\tt{abaab} 然后似了。然而再撤回到开头匹配 s_2 就能正确。

这启发我们考虑如何反悔。是否需要反悔多次呢？仍设 s_2=s_1^k+c，并且先假设有一个串 t 我们要多反悔两次。这就相当于 t=s_1^{k+2}+\dots。多反悔两次相当于撤回 k+2 个 s_1 的匹配，即令 t=s_2+b=s_1^{k}+c+b。由于 b 一定是接上 s_1 或 s_2，可以认为 s_1 是 b 的前缀，于是 t=s_1^{k}+c+s_1+\dots=s_1^{k+2}+\dots。可以得到 c+s_1+\dots=s_1+s_1（注意 c 必须是 s_1 的前缀，长度必然更小）。两个 s_1 可以覆盖自己，则它必然和 c 存在公共循环节，与之前的假设不符。

于是姑且认为只需要多反悔一次即可。

对于 s_1 和 s_2 有公共循环节的部分，先判断 t 是否也有这个公共循环节，剩下的部分相当于给定 a,b,c，求是否有关于方程 ax+by=c 的对于 x,y 的非负整数解。

考虑原问题，我们可以直接暴力地做这些操作！注意到对于短串的长度为 i，我们匹配短串的次数最多为 \frac mi，而 \sum\frac mi 是调和级数，O(m\log m) 可以接受。对于长串，容易发现其出现位置一定不重叠，而长串的长度是 O(n) 的，于是单次时间复杂度 O(\frac mn)，做 n 次是线性。

对于公共循环节的部分，我们不需要任何 exgcd，直接枚举长串的出现次数判断整除即可，时间复杂度同长串匹配，是线性的。

可以使用 hash 或 Z 实现匹配。时间复杂度 O(m\log m)。

关于把暴力匹配改成二分的做法，可以发现用 s=\tt{ab}，t=\tt{ab}^{\frac{m_{\max}}2} 可以卡成 O(m\log m)，所以复杂度理论上还是没啥改进。

这题现在的数据还真是弱爆了，卡不掉二分，卡不掉错误的匹配。从题解看上去像是我造的但是大家其实都不太会造强数据啊，我只是稍微造了点能看的东西吧。不知道后面会不会再加强一下的。

给一个使用二分的代码，在这版数据下跑的挺快。hash 是 SA 改的，所以代码莫名其妙的。

#include<bits/stdc++.h>
using namespace std;
#define base        2310907499
#define MOD         2933256077ll
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define lowbit(x)   ((x)&(-(x)))
#define cntbit(x)   __builtin_popcount(x)
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
mt19937 sd(random_device{}());
int qpow(int a,int b,int m=MOD,int res=1){
    a%=m;
    while(b>0)res=(b&1)?(res*a%m):(res),a=a*a%m,b>>=1;
    return res;
}
int exgcd(int x,int y,int &a,int &b){
    if(y==0){
        a=1;b=0;
        return x;
    }
    int d=exgcd(y,x%y,a,b);
    int z=b;
    b=a-b*(x/y);
    a=z;
    return d;
}
int _x_,_y_;
inline int inverse(int x,int y=MOD){
    exgcd(x,y,_x_,_y_);
    return (_x_+y)%y;
}
int TT;
int h[1000];
uniform_int_distribution<int>rd(0,MOD-1);
struct SA{
    void initbase(int n=10000000){
        p1[0]=p2[0]=1;
        p1[1]=base;p2[1]=inverse(base);
        REP(i,2,n+1)p1[i]=p1[i-1]*p1[1]%MOD,p2[i]=p2[i-1]*p2[1]%MOD;
    }
    string s;
    int n;
    int p1[10000005],p2[10000005];
    int sum[10000005];
    int ask(int l,int r){
        return 1ull*(sum[r+1]+MOD-sum[l])*p2[l]%MOD;
    }
    void build(string S){
        s=S;n=s.size();
        sum[0]=0;
        REP(i,0,n)sum[i+1]=(sum[i]+p1[i+1]*h[s[i]]%MOD)%MOD;
    }
}sa;
int n,m;
bool same(int l,int L,int len){
    return sa.ask(l,l+len-1)==sa.ask(L,L+len-1);
}
bool check(int l,int r,int len,int op=1){
    if(op)l+=n,r+=n;
    if((r-l+1)%len)return 0;
    if(r-l+1==len)return 1;
    return same(l,l+len,r-l+1-len);
}
int getcopies(int x,int rt,int y,int len){
    int l=1,r=(rt-x+1)/len,res=0;
    if(!same(x,y,len))return 0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(x,x+mid*len-1,len,0))res=mid,l=mid+1;
        else r=mid-1;
    }
    return res;
}
string t,s;
int T;
void Main() {
    cin>>m>>n>>s>>t;
    T-=clock();
    sa.build(t+s);
    T+=clock();
    int f=m,g=0;
    for(int i=m-1;i>=1;--i)if(check(0,m-1,i))f=i;
    if(check(0,n-1,f,0)&&same(0,n,f))g=1;
    REP(i,0,m-1){
        int l1=0,l2=i+1,t1=i+1,t2=m-t1;
        if(t1>t2)swap(l1,l2),swap(t1,t2);
        if(t1%f==0&&t2%f==0){
            if(!g){putchar(48);continue;}
            int x=t1/f,y=t2/f,z=n/f,op=0;
            for(int i=0;i*y<=z;++i)if((z-i*y)%x==0){op=1;break;}
            putchar(op+48);
            continue;
        }
        bool f=1;
        int x=0,ct=getcopies(l2+n,l2+t2-1+n,l1+n,t1);
        while(x<n){
            int l=getcopies(x,n-1,l1+n,t1);
            if(x+l*t1==n)break;
            else if(l<ct){f=0;break;}
            else{
                x+=(l-ct)*t1;
                if(x+t2<=n&&same(x,l2+n,t2)){x+=t2;continue;}
            }
            if(l>=ct+1&&x-t1+t2<=n&&same(x-t1,l2+n,t2)){x+=t2-t1;continue;}
            f=0;break;
        }
        putchar(f+48);
    }
    puts("");
}
void TC() {
    sa.initbase();
    REP(i,0,200)h[i]=rd(sd);
    int tc=1;
    cin>>tc;
    while(tc--){
        Main();
        cout.flush();
    }
}
signed main() {
    return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}