ac自动机

贴出来，需要的时候查看和修改。其实基础是trie树，需要理解go和link函数。

  1 #include<bits/stdc++.h>
  2 #define pb push_back
  3 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)
  4 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
  5 typedef long long ll;
  6 using namespace std;
  7 typedef pair<int, int> pii;
  8 const int maxn = 3e6 + 10;
  9 const int M = 2e5 + 123;
 10 struct node {
 11     int term;
 12     int nxt[26];
 13     int link;
 14     int p, ps;
 15     node() {
 16         ps = p = -1;
 17         term = -1;
 18         fill(nxt, nxt + 26, -1);
 19         link = -1;
 20     }
 21 };
 22 int ptr = 1;
 23 node trie[maxn];
 24 
 25 int get_id(const string &s) {
 26     int cur = 0;
 27     for (char cc : s) {
 28         int c = cc - 'a';
 29         if(trie[cur].nxt[c] == -1) {
 30             assert(0);
 31         }
 32         cur = trie[cur].nxt[c];
 33     }
 34     return trie[cur].term;
 35 }
 36 
 37 void add(const string &s, int id) {
 38     int cur = 0;
 39     for (char cc : s) {
 40         int c = cc - 'a';
 41         if(trie[cur].nxt[c] == -1) {
 42             trie[cur].nxt[c] = ptr++;
 43             trie[ptr - 1].p = cur;
 44             trie[ptr - 1].ps = c;
 45         }
 46         cur = trie[cur].nxt[c];
 47     }
 48     trie[cur].term = id;
 49 }
 50 int link(int v);
 51 int go(int v, int c) {
 52     if(trie[v].nxt[c] != -1) {
 53         return trie[v].nxt[c];
 54     }
 55     if(v == 0) return 0;
 56     return trie[v].nxt[c] = go(link(v), c);
 57 }
 58 int link(int v) {
 59     if(trie[v].link != -1) return trie[v].link;
 60     if(v == 0 || trie[v].p == 0) {
 61         return 0;
 62     }
 63     return trie[v].link = go(link(trie[v].p), trie[v].ps);
 64 }
 65 int n, k;
 66 set<int> q[M];
 67 void solve() {
 68     cin >> n >> k;
 69     string s;
 70     cin >> s;
 71     int l = s.size();
 72     s = s + s;
 73     int g;
 74     cin >> g;
 75     for (int i = 0; i < g; i++) {
 76         string t;
 77         cin >> t;
 78         add(t, i + 1);
 79     }
 80     int cur = 0;
 81     for (int i = 0; i < 2 * l; i++) {
 82         cur = go(cur, s[i] - 'a');
 83         if(trie[cur].term != -1) {
 84             int beg = i - k + 1;
 85             if(beg < l) {
 86                 q[beg % k].insert(cur);
 87             }
 88         }
 89     }
 90     for (int i = 0; i < k; i++) {
 91         if(q[i].size() == n) {
 92             cout << "YES" << endl;
 93             for (int j = 0; j < n; j++) {
 94                 cout << get_id(s.substr(i + j * k, k)) << " ";
 95             }
 96             cout << endl;
 97             return;
 98         }
 99     }
100     cout << "NO" << endl;
101 }
102 int main() {
103     freopen("test.in", "r", stdin);
104     //freopen("test.out", "w", stdout);
105     solve();
106     return 0;
107 }

普通的写法，bfs建立失败节点，应该好理解一些！

  1 #include<bits/stdc++.h>
  2 #define pb push_back
  3 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)
  4 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
  5 typedef long long ll;
  6 using namespace std;
  7 typedef pair<int, int> pii;
  8 const int maxn = 1e6 + 10;
  9 int fail[maxn];
 10 int cnt = 0;
 11 int pos[maxn];
 12 struct node {
 13     int nxt[26];
 14     int type;
 15     int l;
 16     node() {
 17         memset(nxt, -1, sizeof nxt);
 18         type = l = 0;
 19     }
 20 } a[maxn];
 21 void add(string s) {
 22     int cur = 0;
 23     for (int i = 0; i < s.size(); i++) {
 24         int id = s[i] - 'a';
 25         if(a[cur].nxt[id] == -1) {
 26             a[cur].nxt[id] = ++cnt;
 27             //cout << cnt << endl;
 28         }
 29         cur = a[cur].nxt[id];
 30     }
 31     a[cur].type = 1;
 32     a[cur].l = s.size();
 33 }
 34 void bt() {
 35     queue<int> q;
 36     fail[0] = 0;
 37     for (int i = 0; i < 26; i++) {
 38         if(a[0].nxt[i] == -1) {
 39             a[0].nxt[i] = 0;
 40         } else {
 41             fail[a[0].nxt[i] ] = 0;
 42             q.push(a[0].nxt[i]);
 43         }
 44     }
 45     while(!q.empty()) {
 46         int now = q.front();
 47         q.pop();
 48         for (int i = 0; i < 26; i++) {
 49             if(a[now].nxt[i] == -1) {
 50                 a[now].nxt[i] = a[fail[now] ].nxt[i];
 51             } else {
 52                 fail[a[now].nxt[i] ] = a[fail[now] ].nxt[i];
 53                 q.push(a[now].nxt[i]);
 54             }
 55         }
 56     }
 57 }
 58 void work(string s) {
 59     memset(pos, 0, sizeof pos);
 60     int now = 0;
 61     for (int i = 0; i < s.size(); i++) {
 62         int id = s[i] - 'a';
 63         now = a[now].nxt[id];
 64         int tmp = now;
 65         while(tmp != 0) {
 66             if(a[tmp].type == 1) {
 67                 pos[i + 1] -= 1;
 68                 pos[i - a[tmp].l + 1 ] += 1;
 69                 //cout << i << endl;
 70                 break;
 71             }
 72             tmp = fail[tmp];
 73         }
 74     }
 75     int cnt = 0;
 76     for (int i = 0; i < s.size(); i++) {
 77         cnt += pos[i];
 78         if(cnt <= 0) cout << s[i];
 79         else cout << "*";
 80     }
 81     cout << endl;
 82 }
 83 void solve() {
 84     int n;
 85     cin >> n;
 86     string s;
 87     for (int i = 1; i <= n; i++) {
 88         cin >> s;
 89         //cout << s << endl;
 90         add(s);
 91     }
 92     bt();
 93     cin >> s;
 94     work(s);
 95 }
 96 int main() {
 97     freopen("test.in", "r", stdin);
 98     //freopen("test.out", "w", stdout);
 99     ios::sync_with_stdio(0);
100     cin.tie(0); cout.tie(0);
101     solve();
102     return 0;
103 }