HDU 3695 Computer Virus on Planet Pandora AC自动机裸题
题目来源:HDU 3695 Computer Virus on Planet Pandora
题意:输入n个字符串 求最后一个字符串有n个字符串中的几种
思路:直接暴力ac自动机
#include <cstdio> #include <cstring> #include <queue> 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 <node*> 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; }
HDU 3695 Computer Virus on Planet Pandora AC自动机裸题,古老的榕树,5-wow.com
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。