AtCoder Regular Contest 55 C - ABCAC
問題概要
文字列Sに対して
S=A+B+C+A+C
となるような部分文字列A, B, Cがいくつ考えうる数え上げる。
解法
部分点
- AとCの文字数を決める
- O(N2)
- 条件を満たすかはローリングハッシュでO(1)
満点
- SをABCとACに分ける境目を探索する
- その際、Z algorithmを使ってAとして考えうる文字列で最長のもの、Cとして考えうる文字列で最長のものを求める
- 上記の値から、境目で分けた場合に考えうるA, B, Cの数を計算する
