題目來源:HDU 3695 Computer Virus on Planet Pandora
題意:輸入n個字符串 求最後一個字符串有n個字符串中的幾種
思路:直接暴力ac自動機
#include#include #include using namespace std; const int maxn = 5200010; char s1[maxn], s2[maxn], s3[maxn]; int ans; struct node { int val; node *next[26]; node *fail; node() { val = 0; for(int i = 0; i < 26; i++) next[i] = NULL; fail = NULL; } }; node *root; void insert(char *s) { int n = strlen(s); node *curr = root; for(int i = 0; i < n; i++) { int c = s[i] - 'A'; if(curr->next[c] == NULL) { node *newnode = new node; curr->next[c] = newnode; } curr = curr->next[c]; } curr->val++; } void build() { root->fail = NULL; queue Q; Q.push(root); while(!Q.empty()) { node *temp = Q.front(); node *p = NULL; Q.pop(); for(int i = 0; i < 26; i++) { if(temp->next[i] == NULL) continue; if(temp == root) temp->next[i]->fail = root; else { p = temp->fail; while(p != NULL) { if(p->next[i] != NULL) { temp->next[i]->fail = p->next[i]; break; } p = p->fail; } if(p == NULL) temp->next[i]->fail = root; } Q.push(temp->next[i]); } } } void find(char *s) { int n = strlen(s); node *p = root; for(int i = 0; i < n; i++) { int c = s[i] - 'A'; while(p != root && p->next[c] == NULL) p = p->fail; p = p->next[c]; if(p == NULL) p = root; node *temp = p; while(temp != root) { if(temp->val > 0) { ans += temp->val; temp->val = 0; temp = temp->fail; } else break; } } } void del(node *p) { for(int i = 0; i < 26; i++) { if(p->next[i] != NULL) del(p->next[i]); } free(p); } void get() { int len = strlen(s1); int sum = 0; int flag = 0; int l = 0; for(int i = 0; i < len; i++) { if(s1[i] == '[') { flag = 1; sum = 0; } else if(s1[i] == ']') { ; } else if(flag) { if(s1[i] >= '0' && s1[i] <= '9') sum = sum * 10 + s1[i] - '0'; else { flag = 0; for(int j = 0; j < sum; j++) s2[l++] = s1[i]; } } else s2[l++] = s1[i]; } s2[l] = 0; s3[l] = 0; int j = l; for(int i = 0; i < l; i++) s3[l-i-1] = s2[i]; } int main() { int T; scanf("%d", &T); while(T--) { ans = 0; root = new node; int n; scanf("%d", &n); while(n--) { char s[1111]; scanf("%s", s); insert(s); } build(); scanf("%s", s1); get(); find(s2); find(s3); printf("%d\n", ans); } return 0; }