https://www.luogu.org/problemnew/show/3808
在Tire上做KMP
- #include < cstdio > #include < queue > #include < iostream > #define FOR(i, s, t) for (register int i = s; i <= t; ++i) using std: :cin;
- const int N = 4000011;
- char s[N];
- int tot,
- n,
- ans;
- namespace AC_automaton {
- struct Tire {
- int cnt,
- fail;
- int to[27];
- }
- tr[N];
- inline void build_tire() {
- int u = 0;
- for (register int i = 0; s[i] != ‘\0‘; ++i) {
- if (!tr[u].to[s[i] - ‘a‘]) tr[u].to[s[i] - ‘a‘] = ++tot;
- u = tr[u].to[s[i] - ‘a‘];
- }++tr[u].cnt;
- }
- inline void build_automaton() {
- int v,
- u;
- std: :queue < int > q;
- FOR(i, 0, 25) if ((v = tr[0].to[i])) q.push(v);
- int now;
- while (!q.empty()) {
- now = q.front();
- q.pop();
- FOR(i, 0, 25) {
- v = tr[now].to[i];
- u = tr[now].fail;
- if (v) {
- tr[v].fail = tr[u].to[i];
- q.push(v);
- } else tr[now].to[i] = tr[u].to[i];
- }
- }
- }
- inline void match() {
- int now = 0,
- tmp;
- for (register int i = 0; s[i] != ‘\0‘; ++i) {
- now = tr[now].to[s[i] - ‘a‘];
- tmp = now;
- while (tmp && tr[tmp].cnt != -1) {
- ans += tr[tmp].cnt;
- tr[tmp].cnt = -1;
- tmp = tr[tmp].fail;
- }
- }
- }
- }
- using namespace AC_automaton;
- int main() {
- scanf("%d\n", &n);
- while (n--) {
- scanf("%s", s);
- build_tire();
- }
- tr[0].fail = 0;
- build_automaton();
- scanf("%s", s);
- match();
- printf("%d\n", ans);
- return 0;
- }