AtCoder Regular Contest 055 C. ABCAC

問題

文字列Sが与えられる。
この文字列は、それぞれ長さ1以上の文字列A,B,Cを「ABCAC」のように連結してできている。
このような分割は何通りあるか？

制約

5<=Sの長さ<=200,000
(部分点：Sの長さ<=2,000)

解法

説明のために、「A B C A' C'」と置く。N=(Sの長さ)とする。

もし、A'が出現する位置がxだとわかったとして、A'の長さが決まれば、C'の長さが決まる。
なので、A=A'となる最大の長さa、C'=Cとなる最大の長さcが高速に求まれば、以下から判定できる。
・a+c<(N-x)ならば、作ることができないので、無し
・x<=(N-x)ならば、Bの部分を作ることができないので、無し
・候補となるA'とC'の最大の長さは、1文字以上である必要があるので、それぞれ、min(a,N-x-1)、min(c,N-x-1)
・このとき、組み合わせの数は、「min(a,N-x-1) + min(c,N-x-1) - (N-x) + 1」で求められる
　・min(a,N-x-1)+min(c,N-x-1)==N-xの場合は、1通り
　・min(a,N-x-1)+min(c,N-x-1)==N-x+1の場合は、2通り
　・、、、

ということで、位置xにおける「A=A'となる最大の長さa」と「C'=Cとなる最大の長さc」を高速に求める必要がある。
エディトリアルではいくつかの方法が紹介されているが、SuffixArrayと高さ配列を使っても解けるので、それを試してみる。

高さ配列は、SuffixArrayが構築されている場合、次の接尾辞とのprefixの一致数をO(N)で求められる。
SuffixArrayの中で、インデクスが0の部分が「Sの先頭からの文字列」を表すので、そこから前後に高さ配列の値が降順になるようにすれば、すべての位置に対する「A=A'となる最大の長さ」を求められる。

インデクス	接尾辞	高さ配列	高さ配列の値をインデクス0から降順になるようにしたもの
11		0	0
10	a	0	0
7	abra	1	1
0	abracadabra	4	4
3	acadabra	1	1
5	adabra	1	1
8	bra	0	0
1	bracadabra	3	0
4	cadabra	0	0
6	dabra	0	0
9	ra	0	0
2	racadabra	2	0

インデクスが0の部分から、高さ配列を前後にそれぞれ降順になるようにしたものが表の一番右。
これは、min()を取りながらO(N)で求められ、これは位置xに対する「A=A'となる最大の長さ」の情報になっている。(ので、O(1)で求められる)

「C'=Cとなる最大の長さc」については、文字列Sをreverseしたものについて同様に行えば、位置x-1で終わるようなCの最大の長さがO(1)で求められる。
したがって、
・SuffixArray構築にO(N)～O(N log^2 N)
・位置xを決めるためにO(N)
・aとcを求めるのにO(1)
・位置xでの組み合わせの数を求めるのにO(1)
なので、全体でO(N)～O(N log^2 N)程度で求められる。

解法2

Z algorithmは上のをO(N)で作ることができる。

//z[i]:=文字列sと、位置iから始まる部分文字列との共通接頭辞の長さ(ただしz[0]=0)
std::vector<int> Zalgorithm(const std::string& s){
  int n = s.length();
  std::vector<int> z(n, 0);

  int L = 0, R = 0;
  for(int i=1; i<n; i++){
    if(i>R){
      L = R = i;
      while(R<n && s[R-L] == s[R]) R++;
      z[i] = R-L;
      R--;
    }else{
      int k = i-L;
      if(z[k] < R-i+1){
        z[i] = z[k];
      }else{
        L = i;
        while(R<n && s[R-L] == s[R]) R++;
        z[i] = R-L;
        R--;
      }
    }
  }
  return z;
}