呵呵，先貼一張圖： "洛谷題目頁面傳送門" & "CodeForces題目頁面傳送門" 給定字元串$a$，求它的每一個首碼，是否能被表示成$m+1$個字元串$A$和$m$個字元串$B$交錯相連的形式，即求$\forall i\in[1,n],\left[\exists A,\exists B,a_{ ...
呵呵，先貼一張圖：（這就是我CodeForces的頭像（至少現在是））
洛谷題目頁面傳送門 & CodeForces題目頁面傳送門
給定字元串\(a\)，求它的每一個首碼，是否能被表示成\(m+1\)個字元串\(A\)和\(m\)個字元串\(B\)交錯相連的形式，即求\(\forall i\in[1,n],\left[\exists A,\exists B,a_{1\sim i}=\underbrace{A+B+A+\cdots+A+B+A}_{m+1\text{個}A,m\text{個}B}\right]\)。
\(|a|\in[1,10^6]\)。
考慮把\(A+B\)看作一個整體，這樣問題就轉化為了求\(a\)的每一個首碼是否能被表示成\(m\)個字元串\(S\)相連再連上一個\(S\)的首碼（可以\(=\varnothing\)，也可以\(=S\)）。
我們先考慮怎麼在短時間內知道一個\(a\)的首碼是否可以被表示為\(m\)個\(S\)相連，如果可以就再往後擴展。這是一個非常經典的問題。設要求的是\(a\)的首碼\(a_{1\sim i}\)。首先，得滿足\(m|i\)，於是我們可以枚舉\(\dfrac im\)，即\(|S|\)。然後如果\(a_{1\sim i-\frac im}=a_{1+\frac im\sim i}\)，那麼\(a_{1\sim i}\)可以被表示為\(m\)個\(S\)相連（這個很好證吧，錯位相等）。我們可以拿\(a_{1+\frac im\sim i}\)去匹配\(a_{1\sim \frac im}\)，這個顯然可以哈希，而在枚舉\(|S|\)時\(a_{1\sim i-\frac im}\)永遠是\(a\)的首碼，所以也可以Z演算法（如果聰明的讀者還不知道Z演算法是什麼，please點擊這個）。
接下來要考慮如何往後拓展。這個比較簡單，往後拓展的那段子串長度一定\(\in[0,|S|]\)，並且要與\(a\)的首碼匹配。這不正是Z演算法的專長嗎？\(\min(|S|,z_{m|S|+1})\)不就是能往後拓展的最長長度嗎？這個最長長度也可以哈希+二分，但那複雜度就帶\(\log\)了。對了，能往後拓展最長\(z_{m|S|+1}\)個，就意味著\(\forall i\in[m|S|,m|S|+z_{m|S|+1}]\)，\(a_{1\sim 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
*/
