首先这就是一道AC自动机板儿题。
可能有重复的模板串情况，所以我每一个节点开一个vector，记录是第几个模板串的结尾。
对于主串，如果不是大写字母，就都默认是第26条出边（'A' ~ 'Z' : 0 ~ 25）。
最后也是最重要的：题面不告诉你有多组数据。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e3 + 5; 21 const int max_len = 2e6 + 5; 22 inline ll read() 23 { 24 ll ans = 0; 25 char ch = getchar(), last = ' '; 26 while(!isdigit(ch)) {last = ch; ch = getchar();} 27 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 28 if(last == '-') ans = -ans; 29 return ans; 30 } 31 inline void write(ll x) 32 { 33 if(x < 0) x = -x, putchar('-'); 34 if(x >= 10) write(x / 10); 35 putchar(x % 10 + '0'); 36 } 37 38 int n; 39 char s[max_len], ss[maxn][55]; 40 int ans[maxn]; 41 42 int ch[maxn * 50][27], f[maxn * 50], cnt = 0; 43 vector<int> val[maxn * 50]; 44 45 void init() 46 { 47 cnt = 0; 48 Mem(ch[0], 0); val[0].clear(); f[0] = 0; 49 Mem(ans, 0); 50 } 51 void insert(int id, char *s) 52 { 53 int len = strlen(s), now = 0; 54 for(int i = 0; i < len; ++i) 55 { 56 int c = s[i] - 'A'; 57 if(!ch[now][c]) 58 { 59 ch[now][c] = ++cnt; 60 val[cnt].clear(); f[cnt] = 0; 61 Mem(ch[cnt], 0); 62 } 63 now = ch[now][c]; 64 } 65 val[now].push_back(id); 66 } 67 void build() 68 { 69 queue<int> q; 70 for(int i = 0; i < 27; ++i) if(ch[0][i]) q.push(ch[0][i]); 71 while(!q.empty()) 72 { 73 int now = q.front(); q.pop(); 74 for(int i = 0; i < 27; ++i) 75 { 76 if(ch[now][i]) f[ch[now][i]] = ch[f[now]][i], q.push(ch[now][i]); 77 else ch[now][i] = ch[f[now]][i]; 78 } 79 } 80 } 81 int getnum(char c) 82 { 83 if(c >= 'A' && c <= 'Z') return c - 'A'; 84 else return 26; 85 } 86 void query(char *s) 87 { 88 int len = strlen(s), now = 0; 89 for(int i = 0; i < len; ++i) 90 { 91 int c = getnum(s[i]); 92 now = ch[now][c]; 93 for(int j = now; j; j = f[j]) 94 for(int k = 0; k < (int)val[j].size(); ++k) ans[val[j][k]]++; 95 } 96 } 97 98 int main() 99 { 100 while(scanf("%d", &n) != EOF) 101 { 102 init(); 103 for(int i = 1; i <= n; ++i) 104 { 105 scanf("%s", ss[i]); 106 insert(i, ss[i]); 107 } 108 build(); 109 scanf("%s", s); 110 query(s); 111 for(int i = 1; i <= n; ++i) if(ans[i]) printf("%s: %d ", ss[i], ans[i]); 112 } 113 return 0; 114 }