呵呵，先贴一张图：（这就是我codeforces的头像（至少现在是））
洛谷题目页面传送门 & codeforces题目页面传送门
给定字符串(a)，求它的每一个前缀，是否能被表示成(m+1)个字符串(a)和(m)个字符串(b)交错相连的形式，即求(forall iin[1,n],left[exists a,exists b,a_{1sim i}=underbrace{a+b+a+cdots+a+b+a}_{m+1text{个}a,mtext{个}b}right])。
(|a|in[1,10^6])。
考虑把(a+b)看作一个整体，这样问题就转化为了求(a)的每一个前缀是否能被表示成(m)个字符串(s)相连再连上一个(s)的前缀（可以(=varnothing)，也可以(=s)）。
我们先考虑怎么在短时间内知道一个(a)的前缀是否可以被表示为(m)个(s)相连，如果可以就再往后扩展。这是一个非常经典的问题。设要求的是(a)的前缀(a_{1sim i})。首先，得满足(m|i)，于是我们可以枚举(dfrac im)，即(|s|)。然后如果(a_{1sim i-frac im}=a_{1+frac imsim i})，那么(a_{1sim i})可以被表示为(m)个(s)相连（这个很好证吧，错位相等）。我们可以拿(a_{1+frac imsim i})去匹配(a_{1sim frac im})，这个显然可以哈希，而在枚举(|s|)时(a_{1sim i-frac im})永远是(a)的前缀，所以也可以z算法（如果聪明的读者还不知道z算法是什么，please点击这个）。
接下来要考虑如何往后拓展。这个比较简单，往后拓展的那段子串长度一定(in[0,|s|])，并且要与(a)的前缀匹配。这不正是z算法的专长吗？(min(|s|,z_{m|s|+1}))不就是能往后拓展的最长长度吗？这个最长长度也可以哈希+二分，但那复杂度就带(log)了。对了，能往后拓展最长(z_{m|s|+1})个，就意味着(forall iin[m|s|,m|s|+z_{m|s|+1}])，(a_{1sim i})都能被表示成(m+1)个字符串(a)和(m)个字符串(b)交错相连的形式，这是个区间答案赋成(1)的操作，可以用线段树或树状数组维护，但更简单的有差分。最后被赋成(1)的次数若(>0)，则答案为(1)，否则为(0)。
感觉说的不太清楚。。。具体看代码吧（也不一定能看懂啊）：
#include<bits/stdc++.h> using namespace std; const int n=1000000; int n/*|a|*/,m/*要被表示成m+1个a与m个b交错相连的形式*/; char a[n+5];//字符串 int z[n+1];//z数组 void z_init(){//z算法 z[1]=n; int zl=0,zr=0; for(int i=2;i<=n;i++) if(zr<i){ while(i+z[i]<=n&&a[i+z[i]]==a[1+z[i]])z[i]++; if(z[i])zl=i,zr=i+z[i]-1; } else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1]; else{ z[i]=zr-i+1; while(i+z[i]<=n&&a[i+z[i]]==a[1+z[i]])z[i]++; zl=i;zr=i+z[i]-1; } } int d[n+1];//差分数组 int main(){ cin>>n>>m>>a+1; z_init(); for(int i=1;i*m<=n;i++)//枚举|s| if(z[i+1]>=i*(m-1)){//a[1~i*m]可以被表示为m个s相连 // cout<<i<<" "<<i*m+min(i,z[i*m+1])<<"n"; d[i*m]++;//往后拓展的左端点差分数组++ if(i*m+min(i,z[i*m+1])+1<=n)d[i*m+min(i,z[i*m+1])+1]--;//往后拓展的右端点的下一个差分数组-- } int now=0; for(int i=1;i<=n;i++){ now+=d[i];//现在now为i的答案被赋成1的次数 cout<<!!now;//转为bool值 } return 0; } /*1 7 2 bcabcab */ /*2 21 2 ababaababaababaababaa */
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/602263.html