Separate String [JAG Practice Contest for ACM-ICPC Asia Regional 2017 H]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_h

N個の文字列集合Sがある。
文字列Tもある。
Tを分解して、全て集合Sの要素となるようにする。
何通りの分割方法があるか(mod10^9+7)

前提知識

• Aho-Corasick

解法

https://jag2017autumn.contest.atcoder.jp/submissions/1794770

M := Tのサイズとしておく
　
まずmod10^9+7数え上げなので、とりあえずDPで考えてみる。
思いつきそうなのが「dp[i] := i番目までの有効な分割の組合せ」
これを愚直に更新していくなら、集合SのサイズがNなので、ちゃんと分割できるかの判定をO(1)でやれてもO(NM)かかる。
しかし、Aho-Corasick法という文字列集合に対して一気にマッチングが行えるアルゴリズムがある。
これを使えばマッチングしている文字列が高速に取り出せる。
マッチングしている文字列を使ってDPを更新すれば答え。

int N, M;
string S[101010], T;
mint dp[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    AhoCorasick ac;
 
    rep(i, 0, N) {
        cin >> S[i];
        ac.add(S[i]);
    }
    ac.build();
 
    cin >> T;
    M = T.size();
    dp[0] = 1;
    int s = ac.root;
    rep(i, 0, M) {
        s = ac.next(s, T[i]);
        fore(j, ac.nodes[s].accept) dp[i + 1] += dp[i - S[j].size() + 1];
    }
    cout << dp[M].get() << endl;
}