題意：給你n個子串（小寫字母， n <= 150, len <= 70）,給你個文本串(len <= 10^6), 讓你找到在文本串中出現次數最多的子串， 輸出最多次數和子串。 注意：如果出現次數最多的有很多子串，要全部輸出，還有n個子串會有重復。 做法：trie的每個節點用一個vector記錄以該節點結尾的單詞的標號，find()函數用數組cnt[]下標保存單詞標號，值保存次數。然後掃描一下即可。 [cpp] #include <cstdio> #include <cstring> #include <queue> #include <vector> #include <algorithm> using namespace std; const int maxn = 10004 * 51; int n; char s[1000006], str[155][77]; int cnt[155]; struct AC { int c[maxn][26], tot, f[maxn]; vector <int> id[maxn]; int idx(char c) { return c-'a'; } int new_node() { memset(c[tot], 0, sizeof(c[tot])); id[tot].clear(); return tot++; } void init() { tot = 0; new_node(); } void insert(char *s, int pos) { int i, j, u = 0, n = strlen(s); for(i = 0; i < n; i++) { int k = idx(s[i]); if(!c[u][k]) c[u][k] = new_node(); u = c[u][k]; } id[u].push_back(pos); } void getfail() { int i, j, u, v; queue <int> q; f[0] = 0; for(i = 0; i < 26; i++) { u = c[0][i]; if(u) { f[u] = 0; q.push(u); } } while(!q.empty()) { u = q.front(); q.pop(); for(i = 0; i < 26; i++) { v = c[u][i]; if(!v) { c[u][i] = c[f[u]][i]; continue; } // 這行是AC自動機改造： 沒改造的是這樣的 if(!v) continue; j = f[u]; while(j && !c[j][i]) j = f[j]; f[v] = c[j][i]; q.push(v); } } } void find(char *s) { int i, j, u = 0, n = strlen(s); for(i = 0; i < n; i++) { int k = idx(s[i]); // while(u && !c[u][k]) u = f[u]; // 改造後的AC自動機，這句話不用寫 u = c[u][k]; for(j = u; j; j = f[j]) { for(int k = 0; k < id[j].size(); k++) cnt[id[j][k]]++; } } } }ac; int main() { int i, j; while( ~scanf("%d", &n) && n) { ac.init(); memset(cnt, 0, sizeof(cnt)); for(i = 1; i <= n; i++) { scanf("%s", str[i]); ac.insert(str[i], i); } ac.getfail(); scanf("%s", s); ac.find(s); int ans = 0; for(i = 1; i <= n; i++) if(ans < cnt[i]) ans = cnt[i]; printf("%d\n", ans); for(i = 1; i <= n; i++) if(ans == cnt[i]) puts(str[i]); } return 0; }
