Censored String [RUPC2018 Day3 G]

前提知識

• Aho-Corasick

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2753249

以下の解法は自信がないです。
ACできたので書いているだけです。
　
貪欲法で解く。
先頭から順番に文字を見ていって、この文字を消さないとPに含まれる文字が出来てしまうという時に消すという貪欲で解く。
前半に消すよりもギリギリの後半に消すほうが、後々有利なのでこのような貪欲を考えた。
問題は「その文字を消さないとPに含まれる文字ができる」ということをどう判定するかであるが、これはAho-Corasickを使おう。
複数文字列を扱う段階でAho-Corasickな感じがあるので、それを軸に考えると思いつく。
Aho-Corasickの状態を遷移させていって受理状態になったら、文字を消して状態をrootに戻す。
これを繰り返して、消した回数を答えると答え。

string S;
int N;
string P[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> N;
    rep(i, 0, N) cin >> P[i];

    AhoCorasick ac;
    rep(i, 0, N) ac.add(P[i]);
    ac.build();

    int ans = 0;
    int cur = ac.root;

    fore(c, S) {
        cur = ac.next(cur, c);
        if (0 < ac.nodes[cur].accept.size()) {
            ans++;
            cur = ac.root;
        }
    }

    cout << ans << endl;
}