题目链接：?pid=3065题目分析：裸的AC自动机，，忽视了只含大写字母，MLE了，注意是多组数据，存一下每个单词和对应的出现次数#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;int const MAX = 2000005;char word[1005][55], text[MAX];int cnt[1005];struct node {int id;bool end;node *next[26];node *fail;node(){id = -1;end = false;memset(next, NULL, sizeof(next));fail = NULL;}};void Insert(node *p, char *s, int id){for(int i = 0; s[i] != '\0'; i++){int idx = s[i] – 'A';if(p -> next[idx] == NULL)p -> next[idx] = new node();p = p -> next[idx];}p -> end = true;p -> id = id;}void AC_Automation(node *root){queue <node*> q;q.push(root);while(!q.empty()){node *p = q.front();q.pop();for(int i = 0; i < 26; i++){if(p -> next[i]){if(p == root)p -> next[i] -> fail = root;elsep -> next[i] -> fail = p -> fail -> next[i];q.push(p -> next[i]);}else{if(p == root)p -> next[i] = root;elsep -> next[i] = p -> fail -> next[i];}}}}bool Query(node *root){bool flag = false;int len = strlen(text);node *p = root;for(int i = 0; i < len; i++){int idx = text[i] – 'A';if(idx < 0 || idx > 25){p = root;continue;}while(!p -> next[idx] && p != root)p = p -> fail;p = p -> next[idx];if(!p){p = root;continue;}node *tmp = p;while(tmp != root){if(tmp -> end){flag = true;cnt[tmp -> id]++;}elsebreak;tmp = tmp -> fail;}}return flag;}int main(){int n;while(scanf("%d", &n) != EOF){memset(cnt, 0, sizeof(cnt));node *root = new node();for(int i = 0; i < n; i++){scanf("%s", word[i]);Insert(root, word[i], i);}AC_Automation(root);getchar();gets(text);if(Query(root))for(int i = 0; i < n; i++)if(cnt[i])printf("%s: %d\n", word[i], cnt[i]);}}
闲淡时光里徜徉书海。本文是旅游开心句子说说心情，希望对大家有帮助！
