专栏文章

题解：CF2053G Naive String Splits

IIvanZhang2009
CF2053G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqmhqps
此快照首次捕获于
2025/12/04 07:13
3 个月前
此快照最后确认于
2025/12/04 07:13
3 个月前
查看原文
先不考虑复杂度，就给你两个串，如何判定是否可以拼出 tt 呢？
我们考虑如何正确地直接贪心。假设 s1,s2\bm{s_1,s_2} 不存在公共循环节，原因后面再说。具体地，设我们试图用字符串 s1,s2s_1,s_2 拼出字符串 tt，且 ∣s1∣≤∣s2∣\lvert s_1\rvert\le \lvert s_2\rvert。此处给定一个贪心：不断地匹配短串 s1s_1，直到匹配不上为止，然后尝试匹配一次 s2s_2。注意到这样可能会出问题，因为如果 s2s_2 有若干个 s1s_1 作为前缀，可能有类似反悔的操作。例如 s1=abs_1=\tt{ab}，s2=ababcs_2=\tt{ababc}。贪心匹配 t=abababct=\tt{abababc} 时，先用 s1s_1 匹配了 33 次，然后直接塞 s2s_2 也不合法，但是由于 s2s_2 包含两次 s1s_1 作为前缀，可以撤销掉这两个匹配重新尝试塞 s2s_2。
形式化地，设 s2=s1k+cs_2=s_1^k+c，我们每次先贪心匹配 s1s_1，然后遇到匹配不了的地方先直接匹配 s2s_2。如果失败了就撤回 kk 次 s1s_1 的匹配，然后接着匹配 s2s_2。如果再失败，其实如果 cc 是 s1s_1 的前缀，可以再撤回一次 s1s_1 并尝试匹配，具体可以手玩下面这个数据中 s1=aba,s2=abaabs_1=\tt{aba},s_2=\tt{abaab} 的情况：
CPP
1
8
abaabaab
abaababa
这个例子里，先匹配了两次 aba\tt{aba}，然后撤回发现 ababa≠abaab\tt{ababa}\neq\tt{abaab} 然后似了。然而再撤回到开头匹配 s2s_2 就能正确。
这启发我们考虑如何反悔。是否需要反悔多次呢？仍设 s2=s1k+cs_2=s_1^k+c，并且先假设有一个串 tt 我们要多反悔两次。这就相当于 t=s1k+2+…t=s_1^{k+2}+\dots。多反悔两次相当于撤回 k+2k+2 个 s1s_1 的匹配，即令 t=s2+b=s1k+c+bt=s_2+b=s_1^{k}+c+b。由于 bb 一定是接上 s1s_1 或 s2s_2，可以认为 s1s_1 是 bb 的前缀，于是 t=s1k+c+s1+⋯=s1k+2+…t=s_1^{k}+c+s_1+\dots=s_1^{k+2}+\dots。可以得到 c+s1+⋯=s1+s1c+s_1+\dots=s_1+s_1（注意 cc 必须是 s1s_1 的前缀，长度必然更小）。两个 s1s_1 可以覆盖自己，则它必然和 cc 存在公共循环节，与之前的假设不符。
于是姑且认为只需要多反悔一次即可。
对于 s1s_1 和 s2s_2 有公共循环节的部分，先判断 tt 是否也有这个公共循环节，剩下的部分相当于给定 a,b,ca,b,c，求是否有关于方程 ax+by=cax+by=c 的对于 x,yx,y 的非负整数解。
考虑原问题，我们可以直接暴力地做这些操作！注意到对于短串的长度为 ii，我们匹配短串的次数最多为 mi\frac mi，而 ∑mi\sum\frac mi 是调和级数，O(mlog⁡m)O(m\log m) 可以接受。对于长串，容易发现其出现位置一定不重叠，而长串的长度是 O(n)O(n) 的，于是单次时间复杂度 O(mn)O(\frac mn)，做 nn 次是线性。
对于公共循环节的部分，我们不需要任何 exgcd，直接枚举长串的出现次数判断整除即可，时间复杂度同长串匹配，是线性的。
可以使用 hash 或 Z 实现匹配。时间复杂度 O(mlog⁡m)O(m\log m)。
关于把暴力匹配改成二分的做法，可以发现用 s=abs=\tt{ab}，t=abmmax⁡2t=\tt{ab}^{\frac{m_{\max}}2} 可以卡成 O(mlog⁡m)O(m\log m)，所以复杂度理论上还是没啥改进。
这题现在的数据还真是弱爆了，卡不掉二分，卡不掉错误的匹配。从题解看上去像是我造的但是大家其实都不太会造强数据啊，我只是稍微造了点能看的东西吧。不知道后面会不会再加强一下的。
给一个使用二分的代码，在这版数据下跑的挺快。hash 是 SA 改的，所以代码莫名其妙的。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...