CFR 526 D. Om Nom and Necklace ( KMP, Periodic )

Problem - D - Codeforces

題意：
給長度 N 的字串，以及定數 K。
對於 i = [ 0 .. N - 1 ]，問是否存在字串 A 和 B，使得 A + B + A + B .. + A = S[ 0 .. i ]，其中 A 重複 K + 1 次，B 重複 K 次。
A, B 可為空字串。

制約：
1 ≤ N, K ≤ 1e6

解法：
KMP 真是蛋疼難。
跟這題有六分像。
總之 KMP 得到的 Fail 數組的定義如下：
Fail[ i ] + 1：S[ 0 .. i ] 的前綴和後綴的最長共同長度。
所以 i + 1 - ( Fail[ i ] + 1 ) 就是最小循環節長度 ( 接一接可能會超出去 )。
可以知道，A + B 必須是以這個循環節為基礎，也就是說可以用若干個最小循環節表示。
接著可以知道，如果有解，A + B 一定可以用 ( i + 1 ) / K 這麼多個最小循環節，並且 A 會用 ( i + 1 ) % K 這麼多個最小循環節 ( 後面也許會有最小循環節的片段，但先不管 )。
原因是，A 越短越好，因為 A + B 用的最小循環節個數不能少於 A 用的，除此之外沒什麼特別的限制。
一共要用的最小循環節數量 cnt 一定是 ( i + 1 ) / 最小循環節長度。
如果可以整除，那麼判斷剛剛說的限制就可以了。
否則，因為最後一個 A 一定會伴隨最小循環節的不完整片段，所以 B 一定也會有。因此 B 不能為空字串。這要特別判，因為這個渣渣的部分在前面的計算被 truncated。

複雜度：
O( N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e6 );

int N, K;
string S;
int F[ MAXN ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> K;
  cin >> S;
  int fptr = F[ 0 ] = -1;
  for( int i = 1; i < N; ++i ) {
    while( fptr != -1 and S[ fptr + 1 ] != S[ i ] ) fptr = F[ fptr ];
    if( S[ fptr + 1 ] == S[ i ] ) ++fptr;
    F[ i ] = fptr;
  }
  for( int i = 0; i < N; ++i ) {
    if( i + 1 < K ) {
      cout << 0;
      continue;
    }
    int cyc_len = ( i + 1 ) - ( F[ i ] + 1 );
    int cnt = ( i + 1 ) / cyc_len;
    if( ( i + 1 ) % cyc_len == 0 ) {
      cout << "01"[ cnt / K >= cnt % K ];
    } else {
      cout << "01"[ cnt / K > cnt % K ];
    }
  }
  cout << endl;
  return 0;
}