/* hdu 3695 TLE 题 */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; #define MAXN 5100010 #define MAX 1010 #define N 27 int Case , n , cnt; bool vis[MAX]; char text[MAXN]; char tmpStr[MAXN]; char tmp[MAXN]; struct Node{ Node *next; Node *child[N]; int number; }; Node node[MAXN]; Node *root; queue<Node*>q; Node* newNode(){ node[cnt].next = NULL; node[cnt].number = 0; for(int i = 0 ; i < N ; i++) node[cnt].child[i] = NULL; return &node[cnt++]; } void insert(char *str , int x){ int len = strlen(str); Node *p = root; for(int i = 0 ; i < len ; i++){ int num = str[i]-'A'; if(p->child[num] == NULL) p->child[num] = newNode(); p = p->child[num]; } p->number = x; } void init(){ int pos = 0; int len = strlen(tmpStr); memset(text , '\0' , sizeof(text)); for(int i = 0 ; i < len ; i++){ if(isupper(tmpStr[i])) text[pos++] = tmpStr[i]; else if(tmpStr[i] == '[' || tmpStr[i] == ']') continue; else if(isdigit(tmpStr[i])){ int num = 0; while(isdigit(tmpStr[i])) num = num*10+tmpStr[i++]-'0'; memset(tmp , tmpStr[i] , sizeof(tmp)); tmp[num] = '\0'; strcat(text , tmp); pos += num; } } } void getNext(){ while(!q.empty()) q.pop(); q.push(root); root->next = NULL; while(!q.empty()){ Node *p = q.front(); q.pop(); for(int i = 0 ; i < N ; i++){ if(p->child[i]){ q.push(p->child[i]); Node* tmp = p->next; while(tmp){ if(tmp->child[i]){ p->child[i]->next = tmp->child[i]; break; } tmp = tmp->next; } if(tmp == NULL) p->child[i]->next = root; } } } } int find(){ Node *p = root; int len = strlen(text); int ans = 0; for(int i = 0 ; i < len ; i++){ int num = text[i]-'A'; while(p->child[num] == NULL && p != root) p = p->next; if(p->child[num]){ p = p->child[num]; Node *tmp = p; while(tmp){ if(tmp->number && !vis[tmp->number]){ ans++; vis[tmp->number] = true; } tmp = tmp->next; } } } return ans; } int main(){ char str[MAX]; scanf("%d" , &Case); while(Case--){ scanf("%d" , &n); cnt = 0; root = newNode(); memset(vis , false , sizeof(vis)); for(int i = 0 ; i < n ; i++){ scanf("%s" , str); insert(str , i+1); int len = strlen(str); reverse(str , str+len); insert(str , i+1); } getNext(); scanf("%s" , tmpStr); init(); printf("%d\n" , find()); } return 0; }
时间: 2024-07-31 13:24:08