HDU-3695 Computer Virus on Planet Pandora

 ?1 #include<bits/stdc++.h> ?2 using namespace std; ?3 #define LL long long ?4 #define ULL unsigned LL ?5 #define fi first ?6 #define se second ?7 #define lson l,m,rt<<1 ?8 #define rson m+1,r,rt<<1|1 ?9 #define max3(a,b,c) max(a,max(b,c)) 10 #define min3(a,b,c) min(a,min(b,c)) 11 const int INF = 0x3f3f3f3f; 12 const LL mod = 1e9+7; 13 typedef pair<int,int> pll; 14 const int N = 1e6+10; 15 int tot = 2; 16 char str[N*26], tmp[N*26]; 17 int trie[N*4][26], cnt[N*26], fair[N*26]; 18 void init(){ 19 ????for(int i = 1; i < tot; i++){ 20 ????????for(int j = 0; j < 26; j++) 21 ????????????trie[i][j] = 0; 22 ????} 23 ????tot = 2; 24 } 25 void Insert(){ 26 ????int rt = 1, len = strlen(str); 27 ????for(int i = 0; i < len; i++){ 28 ????????int id = str[i] - ‘A‘; 29 ????????if(!trie[rt][id]) { 30 ????????????cnt[tot] = 0; 31 ????????????fair[tot] = 0; 32 ????????????trie[rt][id] = tot++; 33 ????????} 34 ????????rt = trie[rt][id]; 35 ????} 36 ????cnt[rt]++; 37 } 38 void Build_tree(){ 39 ????queue<int> q; 40 ????q.push(1); 41 ????int p; 42 ????while(!q.empty()){ 43 ????????int tmp = q.front(); 44 ????????q.pop(); 45 ????????for(int j = 0; j < 26; j++){ 46 ????????????if(trie[tmp][j]){ 47 ????????????????if(tmp == 1) 48 ????????????????????fair[trie[tmp][j]] = 1; 49 ????????????????else { 50 ????????????????????p = fair[tmp]; 51 ????????????????????while(p){ 52 ????????????????????????if(trie[p][j]){ 53 ????????????????????????????fair[trie[tmp][j]] = trie[p][j]; 54 ????????????????????????????break; 55 ????????????????????????} 56 ????????????????????????else p = fair[p]; 57 ????????????????????} 58 ????????????????????if(!p) fair[trie[tmp][j]] = 1; 59 ????????????????} 60 ????????????????q.push(trie[tmp][j]); 61 ????????????} 62 ????????} 63 ????} 64 } 65 int Find(int len){ 66 ????int ret = 0, rt = 1; 67 ????for(int i = 0; i < len; i++){ 68 ????????int id = str[i] - ‘A‘; 69 ????????while(rt != ?1 && !trie[rt][id]) rt = fair[rt];; 70 ????????if(trie[rt][id]) rt = trie[rt][id]; 71 ????????int p = rt; 72 ????????while(p != 1){ 73 ????????????if(cnt[p] >= 0){ 74 ????????????????ret += cnt[p]; 75 ????????????????cnt[p] = -1; 76 ????????????} 77 ????????????else break; 78 ????????????p = fair[p]; 79 ????????} 80 ????} 81 ????rt = 1; 82 ????for(int i = len - 1; i >= 0; i--){ 83 ????????int id = str[i] - ‘A‘; 84 ????????while(rt != ?1 && !trie[rt][id]) rt = fair[rt]; 85 ????????if(trie[rt][id]) rt = trie[rt][id]; 86 ????????int p = rt; 87 ????????while(p != 1){ 88 ????????????if(cnt[p] >= 0){ 89 ????????????????ret += cnt[p]; 90 ????????????????cnt[p] = -1; 91 ????????????} 92 ????????????else break; 93 ????????????p = fair[p]; 94 ????????} 95 ????} 96 ????return ret; 97 } 98 int main(){ 99 ????int t;100 ????scanf("%d", &t);101 ????while(t--){102 ????????int n;103 ????????init();104 ????????scanf("%d", &n);105 ????????while(n--){106 ????????????scanf("%s", str);107 ????????????Insert();108 ????????}109 ????????Build_tree();110 ????????scanf("%s", tmp);111 ????????int len = strlen(tmp);112 ????????int ccc = 0;113 ????????for(int i = 0; i < len; i++){114 ????????????if(tmp[i] != ‘[‘){115 ????????????????str[ccc++] = tmp[i];116 ????????????}117 ????????????else {118 ????????????????int _c = 0;119 ????????????????i++;120 ????????????????while(isdigit(tmp[i]))121 ????????????????????_c = _c *10 + (int)(tmp[i]-‘0‘), i++;122 ????????????????while(_c--)123 ????????????????????str[ccc++] = tmp[i];124 ????????????????i++;125 ????????????}126 ????????}127 ????????printf("%d\n", Find(ccc));128 ????}129 ????return 0;130 }