AC自動機，就相當于是在字典樹上用kmp。next數組回退的位置為最大匹配字符串在字典樹上的節點位置。

在獲取字典樹上的next數組的時候用的是BFS每次相當與處理的一層。

下圖中紅線為，可以回退的位置，沒有紅線的節點回退的位置都是虛擬原點。

int n, m;
int o[N];
int tr[N][26], cnt[N], idx;
char str[N];
int q[N], ne[N];inline void insert() { // 正常的字典樹插入板子int p = 0;for(int i = 0; str[i]; i ++) {int t = str[i] - 'a';if(!tr[p][t]) tr[p][t] = ++ idx;p = tr[p][t];}cnt[p] ++; // 記錄當前字符串出現的次數
}void build() {int  hh = 0, tt = -1;for(int i = 0; i < 26; i ++) // 因為第二層的所有字符串長度為一，next值肯定為1，直接入隊即可if(tr[0][i])q[++ tt] = tr[0][i];while(hh <= tt) {int t = q[hh ++];for(int i = 0; i < 26; i ++) {int p = tr[t][i];if(!p) tr[t][i] = tr[ne[t]][i]; // 匹配失敗，則回退，路徑壓縮過，一次回退即可else {ne[p] = tr[ne[t]][i]; // 記錄ne數組，順便壓縮路徑q[ ++ tt] = p;}}}
}inline void sovle() {idx = 0;cin >> n;for(int i = 0; i < n; i ++) {cin >> str;insert(); // 將所有字符串全都插入字典樹}build(); // 獲取next數組cin >> str;int res = 0;int s = 0;for(int i = 0, j = 0; str[i]; i ++) { // 同時匹配字典樹中所有的字符串int t = str[i] - 'a';j = tr[j][t];int p = j;while(p && cnt[p] != 0) { // 線性匹配，這里的第二個條件是一個優化，只有在每個字符串只記錄一次的前提下使用res += cnt[p]; // 記錄出現過的字符串的個數cnt[p] = 0; // 因為每個字符串只計算一次，所以要清空p = ne[p]; // 回退}}cout << res << endl;
}

與上一題不一樣的只有一小部分，這題中，每個字符串可重復記錄，所以就不能加上那個線性優化，還需要記錄每個字符串出現的次數即可。

int n, m;
int o[N];
int tr[N][26], cnt[N], idx;
string sr[200];
char str[N];
int q[N], ne[N], st[N];inline void insert(string s) {int p = 0;for(int i = 0; i < s.size(); i ++) {int t = s[i] - 'a';if(!tr[p][t]) tr[p][t] = ++ idx;p = tr[p][t];}cnt[p] ++;
}void build() {int  hh = 0, tt = -1;for(int i = 0; i < 26; i ++)if(tr[0][i])q[++ tt] = tr[0][i];while(hh <= tt) {int t = q[hh ++];for(int i = 0; i < 26; i ++) {int p = tr[t][i];if(!p) tr[t][i] = tr[ne[t]][i];else {ne[p] = tr[ne[t]][i];q[ ++ tt] = p;}}}
}int query(string s) { // 與插入差不多 些許操作不同int p = 0;for(int i = 0; i < s.size(); i ++) {int t = s[i] - 'a';if(!tr[p][t]) return 0;p = tr[p][t];}return st[p];
}inline void sovle() {while(cin >> n, n) {memset(tr, 0, sizeof tr);memset(cnt, 0, sizeof cnt);memset(ne, 0, sizeof ne);memset(st, 0, sizeof st);idx = 0;for(int i = 0; i < n; i ++) {cin >> sr[i];insert(sr[i]);}build();cin >> str;int res = 0;int s = 0;for(int i = 0, j = 0; str[i]; i ++) {int t = str[i] - 'a';j = tr[j][t];int p = j;while(p) {st[p] += cnt[p]; // 記錄該字符串出現的次數s = max(st[p], s); // 因為要求出來最多出現的字符串的次數p = ne[p]; // 回退}}cout << s << endl;for(int i = 0; i < n; i ++) {int k = query(sr[i]); // 字典樹的查詢操作，查詢st數組。if(s == k) cout << sr[i] << endl; // 是最大的直接輸出。}}
}