题意：给出n个文本和m个模板，求每个文本中所有模板出现的总次数。
思路：Trie树权值记录每个模板的个数，，对于每个文本跑一边find即可。
#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<iostream>#include<algorithm>#include<vector>#include<map>#include<queue>#include<stack>#include<string>#include<map>#include<ctime>#include<set>#define eps 1e-6#define LL long long#define pii (pair<int, int>)//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;//const int INF = 0x3f3f3f3f;int n, k, shit;const int maxn = 1000000 + 100;const int SIGMA_SIZE = 26;const int maxnode = 1000000+100;int ch[maxnode][SIGMA_SIZE+5]; int val[maxnode], cnt[100000+1000]; int idx(char c) {return c – 'a';}struct Trie {int sz;Trie() { sz = 1; memset(ch[0], 0, sizeof(ch[0]));};void insert(char *s) {int u = 0, n = strlen(s);for(int i = 0; i < n; i++) {int c = idx(s[i]);if(!ch[u][c]) {memset(ch[sz], 0, sizeof(ch[sz]));val[sz] = 0;ch[u][c] = sz++;}u = ch[u][c];}val[u]++;} };//ac自动机int last[maxn], f[maxn];void print(int i, int j) {if(j) {shit += val[j]; //cout << i << endl;print(i, last[j]);}} int getFail() {queue<int> q;f[0] = 0;for(int c = 0; c < SIGMA_SIZE; c++) {int u = ch[0][c];if(u) {f[u] = 0; q.push(u); last[u] = 0;}}while(!q.empty()) {int r = q.front(); q.pop();for(int c = 0; c < SIGMA_SIZE; c++) {int u = ch[r][c];if(!u) {ch[r][c] = ch[f[r]][c];continue;}q.push(u);int v = f[r];while(v && !ch[v][c]) v = f[v];f[u] = ch[v][c];last[u] = val[f[u]] ? f[u] : last[f[u]];}}}void find_T(char* T) {int len = strlen(T); //cout << len << endl;int j = 0;for(int i = 0; i < len; i++) {int c = idx(T[i]);j = ch[j][c];if(val[j]) print(i, j);else if(last[j]) print(i, last[j]);}} string text[100000+100];char tmp[10050], tt[105000];int ans[100000+10000];int main() {//freopen("input.txt", "r", stdin);int T; cin >> T;while(T–) {scanf("%d%d", &n, &k);memset(ans, 0, sizeof(ans[0])*(n+10));Trie trie;for(int i = 0; i < n; i++) {scanf("%s", tmp);text[i] = tmp;}for(int i = 0; i < k; i++) {scanf("%s", tmp); //cout << tmp << endl;trie.insert(tmp);}getFail();for(int i = 0; i < n; i++) {shit = 0;find_T((char*)text[i].c_str());ans[i] = shit;}for(int i = 0; i < n; i++) printf("%d\n", ans[i]);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
就看你能不能战胜它。战胜了，你就是英雄，就是生活的强者。
