First Second [AtCoder Grand Contest 047 B]

https://atcoder.jp/contests/agc047/tasks/agc047_b

前提知識

• Trie （想定解）
• ローリングハッシュ （hamayanhamayan解法）

解説

https://atcoder.jp/contests/agc047/submissions/15795474

複数文字列なので、最初にTrieが思い浮かんだが、よくよく考えると実装が面倒なので、ロリハに変えた。
まあ、ロリハライブラリもバグり倒していたので、結局むっちゃかかった。

条件を言い換える

まず、文字列aを文字列bにできるかというのを考える。
自明な所から考えると、文字列の長さは|a|≧|b|でなくてはならない。
先頭2文字だけ操作できるということは、ストックできるのは1文字だけということになる。
そして、ストックすると必ず先頭の文字列になってしまうので、ストックするのは文字列bの先頭になる。
文字列bの先頭を持つと、その後は消すしかできないので、文字列aの末尾をどれだけ残すかという感じになる。

端的に条件を言い換えると、以下をすべて満たせば変換可能。

• |a|≧|b|
• bの先頭以外の末尾列と、同じ長さのaの末尾列が等しい
• bの先頭の文字が、aの↑の条件の末尾列以外の部分に含まれる

末尾といえば、suffix-arrayであるが、複数文字列なので怪しい所。
末尾を考えるよりも先頭を考えた方がよさそうだ。
以降は、文字列をリバースして、

• |a|≧|b|
• bの末尾以外の先頭列と、同じ長さのaの先頭列が等しい
• bの末尾の文字が、aの↑の条件の先頭列以外の部分に含まれる

として考えることにしよう。

先頭が等しくて、末尾の文字が含まれる？

文字列が等しいことを評価するにはローリングハッシュが使える。
ロリハを知らない場合はこの解法は難しい。
どこかで学んでこよう。
文字列を長さでソートして、以下の配列を作っていこう。

cnt[lst][hash] := 最後の文字がlstで、それ以外の文字列をハッシュ化するとhashとなる組は何通りか

これを作って置いて、ある文字列の評価になったときに、その文字列から変換可能な文字を考えていく。
文字列の長さを小さい順からやっていけば、ある文字列の評価時に、変換先の候補となる組はすべてcntに入っている状態を保てる。
文字列を後ろから見ていき、どの文字が含まれるかを持ちながら数え上げていく。

• 以下操作を文字列の末尾から行っていく
  • mskに今見ている文字列を入れる
  • 今見ている文字列より前にある先頭列をhash化する -> hh
  • mskが立っている（先頭列より後にその文字が含まれる）文字cに対してcnt[c][hh]の個数を見て、それを答えに足す

ハッシュの数は大きくなるので、mapに入れる必要がある。
mapに入れるものは遷移先と遷移元の2パターンがあるが、本解法では遷移先を入れている。
こうするとmapに入れる最大個数は2*10⁵個となる。
実装を変えると、mapに入れる最大個数は10⁶となり、自分の解法ではTLEしてしまった。

int N;
string S[201010];
map<ll, int> cnt[26];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];
    rep(i, 0, N) reverse(all(S[i]));
    sort(S, S + N, [&](string a, string b) { return a.length() < b.length(); });

    ll ans = 0;
    
    RollingHash rh;
    rep(i, 0, N) {
        rh.init(S[i]);
        int n = S[i].length();
        
        int msk = 0;
        rrep(j, n - 1, 0) {
            msk |= (1 << (S[i][j] - 'a'));
            ll hh = rh.llhash(0, j - 1);
            rep(c, 0, 26) if ((msk & (1 << c)) && cnt[c].count(hh)) {
                ans += cnt[c][hh];
            }
        }

        ll h = rh.llhash(0, n - 2);
        cnt[S[i][n - 1] - 'a'][h]++;
    }

    cout << ans << endl;
}