Strings of Eternity [AtCoder Beginner Contest 135 F]

https://atcoder.jp/contests/abc135/tasks/abc135_f

前提知識

• Suffix Array
• トポロジカルソート

解説

https://atcoder.jp/contests/abc135/submissions/6588977

まずは尖ったケースを考えてみる。
-1が尖っているので、この辺から考えてみる。
まずは、-1となるケースはこんなケースである
|S|T|
|==|==|
|aa|aaaaaaa|
|ab|abab|
|cab|abcabc|
この辺の例を見てみると、文字列の周期性がキーになっている感じがする。
これはSを伸ばすとcabcabcabcabcabのようにある地点からabcabcがループするので、無限に作れる。
判定するにはTが周期的に何個作れるかというのを考えて行けば良さそう。
これを考えるにはSを任意個くっつけるというよりかは、無限個くっつけた所から探すというのが考えるにはわかりやすい。

これで全探索できそうなパラメタが揃ってきた。
Sのi番目を先頭として、Tを何個作ることができるか。
無限に作れるなら答えは-1である。
Sのi番目は無限個くっつけた2個目以降で考えてもしょうがないので、O(|S|)通り。
あとは、これが効率よく計算できれば、ACが取れる。

Sの長さがTの長さに満たない場合は、計算が若干厄介になるので、Sを何個か結合してTの長さにしておこう。
ok[i] := S[i]から文字列Tを連続で作れるかどうか
これを判定したい。
Sはループしてくる可能性があり、それも面倒なので、S+SにTが含まれるかを判定することにしよう。
ここまで来ると、これは文字列のマッチング問題となり、いろいろな解決法がある。
自分はこの実装にはSuffixArrayを使った。
S+S+"#"+Tという文字列をSuffixArrayに入れてマッチングする方法である。
他にも馴染みのある方法があれば、そちらを使って問題ない。

ok[i]が分かれば、後は、グラフ問題に帰着するので、トポロジカルソートしてDPすればいい。
ok[i]=trueであれば、S[i]からS[i+|T|]へ有向辺を貼る。
このようにできた有向グラフの最長パスが答え。
トポロジカルソートする段階でループも発見できるので、ループがあれば-1

string S, T;
int NS, NT;
int dp[2010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> T;
    string s = S;
    while (S.length() < T.length()) S += s;
    NS = S.length();
    NT = T.length();

    string match = S + S + "#" + T;
    SuffixArraySAIS sais(match);
    TopologicalSort ts(NS);
    
    rep(i, 0, NS) {
        if (sais.common_prefix(i, NS * 2 + 1) == NT) {
            ts.add_edge(i, (i + NT) % NS);
        }
    }

    vector<int> ord;
    bool res = ts.sort(ord);
    if (res == false) {
        cout << -1 << endl;
        return;
    }

    int ans = 0;
    fore(cu, ord) {
        chmax(ans, dp[cu]);
        fore(to, ts.E[cu]) chmax(dp[to], dp[cu] + 1);
    }
    cout << ans << endl;
}