前提知識
解法
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; }