题目链接
中文题题意不解释了。
依旧稍微改一下ac自动机模版就能过了。还有一个坑点！是多组数据！！！
#include#include #include #include using namespace std;const int M = 5e4 + 10 , MM = 2e6 + 10 , N = 1e3 + 10;char str[N][60] , sl[MM];int Next[M][27] , fail[M] , End[M] , c[M / 10] , L , root , cnt , ans;int newnode() { for(int i = 0 ; i <= 26 ; i++) { Next[L][i] = -1; } End[L++] = 0; return L - 1;}void init() { L = 0 , ans = 0; root = newnode(); memset(c , 0 , sizeof(c));}void build(char s[]) { int len = strlen(s); int now = root; for(int i = 0 ; i < len ; i++) { int id = s[i] - 'A'; if(Next[now][id] == -1) { Next[now][id] = newnode(); } now = Next[now][id]; } End[now] = ++ans;}void get_fail() { queue q; fail[root] = root; for(int i = 0 ; i <= 26 ; i++) { if(Next[root][i] == -1) { Next[root][i] = root; } else { fail[Next[root][i]] = root; q.push(Next[root][i]); } } while(!q.empty()) { int now = q.front(); q.pop(); for(int i = 0 ; i <= 26 ; i++) { if(Next[now][i] == -1) { Next[now][i] = Next[fail[now]][i]; } else { fail[Next[now][i]] = Next[fail[now]][i]; q.push(Next[now][i]); } } }}void match(char s[]) { int len = strlen(s); int now = root; for(int i = 0 ; i < len ; i++) { int id; if(s[i] <= 'Z' && s[i] >= 'A') { id = s[i] - 'A'; } else { id = 26; } now = Next[now][id]; int tmp = now; while(tmp != root) { if(End[tmp] > 0) { c[End[tmp]]++; } tmp = fail[tmp]; } }}int main(){ int n; while(scanf("%d" , &n) != EOF) { init(); for(int i = 0 ; i < n ; i++) { scanf("%s" , str[i + 1]); build(str[i + 1]); } getchar(); get_fail(); gets(sl); match(sl); for(int i = 0 ; i < n ; i++) { if(c[i + 1] != 0) { printf("%s: %d\n" , str[i + 1] , c[i + 1]); } } } return 0;}