题意：给出n个病毒的模式串，问每个病毒串在文本串中出现了多少次。
思路：ac自动机。模式串只由大写字母组成。文本串是所有可视字符。 如果动态128会MLE.做法是换成静态数组写法，或者对于每次Search的时候，出现非大写字母的字符特判一下。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 |
/* *********************************************** Author :111qqz Created Time :2016年08月18日 星期四 00时17分38秒 File Name :code/hdu/3065.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <deque> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int sizTrie = 26; map<int,int>mp; char ill[1005][50]; struct Trie { struct Node { Node *nxt[sizTrie]; Node *fail; int cnt; int id; Node() { for ( int i = 0 ; i < sizTrie; i++) nxt[i]=NULL; cnt = 0 ; id = 0 ; fail = NULL; } }; Node *root; void init() { root = new Node(); } void Insert(char *s,int x) { int len = strlen(s); Node *u = root; for ( int i = 0 ; i < len ; i++ ) { int v = s[i]-'A'; if (u->nxt[v]==NULL) u->nxt[v] = new Node(); u = u->nxt[v]; } u->cnt++; u->id = x; // cout<<"s:"<<s<<" cnt:"<< u->cnt <<endl; } void getFail() { root->fail = root; queue<Node*>Q; for ( int i = 0 ; i < sizTrie ; i++) { if (root->nxt[i]==NULL) root->nxt[i] = root; else { root->nxt[i]->fail = root; Q.push(root->nxt[i]); } } while (!Q.empty()) { Node * cur = Q.front(); Q.pop(); for ( int i = 0 ; i < sizTrie ; i++) { if (cur->nxt[i]==NULL) cur->nxt[i] = cur->fail->nxt[i]; else { cur->nxt[i]->fail = cur->fail->nxt[i]; Q.push(cur->nxt[i]); } } } } void Search(char *s) { int len = strlen(s); Node *u = root; mp.clear(); for ( int i = 0 ; i < len ; i++) { if (s[i]<'A'||s[i]>'Z') { u = root; //不要忘记，出现不可能被匹配的字符，相当于重新初始化了 continue; } int v = s[i]-'A'; u = u->nxt[v]; Node * tmp = u; while (tmp!=root) { if (tmp->id) mp[tmp->id]++; tmp = tmp->fail; } } for (auto it = mp.begin() ; it!=mp.end() ; it++) // if (strcmp(ill[it->fst],"")!=0) printf("%s: %d\n",ill[it->fst],it->sec); /* //sort(ans.begin(),ans.end()); int siz = ans.size(); cout<<"anszie:"<<ans.size()<<endl; for ( int i = 0 ; i < siz; i++) { printf("%s: %d\n",ill[ans[i].fst],ans[i].sec); } */ } }ac; const int N=2E6+7; int n; char str[N]; int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif while (scanf("%d",&n)!=EOF) { ac.init(); for ( int i = 1 ; i <= n ; i++) { scanf("%s",ill[i]); ac.Insert(ill[i],i); } ac.getFail(); scanf("%s",str); // cout<<"str:"<<str<<endl; ac.Search(str); } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人！