题意:
多模式串匹配,输出模式串的ID
思路:
典型AC自动机.
用向量存储答案ID
#include <cstdio> #include <cstring> #include <queue> #include <vector> #include <string> #include <algorithm> using namespace std; const int MAXL = 130; /* inline int GetID(char x) { return x; }*/ class node{ public: node* chd[MAXL]; node* fail; int cnt; node(){ fail = NULL; memset(chd,0,sizeof(chd)); cnt = 0; } }; vector <int> ans; class AC_Automation{ public: node* root; queue<node*> q; AC_Automation(){ root = new node; while(!q.empty()) q.pop(); } void insert(string s,int x) { node* cur = root; for(int i=0;i<s.length();i++) { int index = s[i]; if(cur->chd[index] == NULL) cur->chd[index] = new node; cur = cur->chd[index]; } cur->cnt = x; } void BuildAC() { node *cur,*tmp; q.push(root); while(!q.empty()) { cur = q.front(); q.pop(); for(int i = 0; i < MAXL ; i++ ) { if(cur->chd[i]) {//只有root->fail = NULL; if(cur==root) cur->chd[i]->fail = root; else { tmp = cur->fail; while(tmp->fail && !tmp->chd[i]) tmp = tmp->fail; if(tmp->chd[i]) cur->chd[i]->fail = tmp->chd[i]; else cur->chd[i]->fail = root; } q.push(cur->chd[i]); } } } } void query(string s) {//用指针时,指向根节点和指向空要分别对待;在fail的构造中已经解决了指向根的跳回 //只需要注意指向空的时候跳回指向根 node *cur = root, *tmp; for(int i=0;i<s.length();i++) { int index = s[i]; if(cur->chd[index]) cur = cur->chd[index]; else { while(cur && !cur->chd[index]) cur = cur->fail; if(!cur) cur = root; if(cur->chd[index]) cur = cur->chd[index]; } tmp = cur; while(tmp->fail && tmp->cnt) { ans.push_back(tmp->cnt); if(ans.size()==3) return; tmp = tmp->fail; } } } }; char pat[205],tar[10005]; int main() { int n; while(scanf("%d",&n)==1) { AC_Automation AC; for(int i=1; i<=n; i++) { getchar(); gets(pat); AC.insert(pat,i); } AC.BuildAC(); int m,tot = 0; scanf("%d",&m); for(int i=1;i<=m;i++) { getchar(); gets(tar); ans.clear(); AC.query(tar); if(ans.size()) { sort(ans.begin(),ans.end()); printf("web %d:",i); for(int j=0;j<ans.size();j++) printf(" %d",ans[j]); puts(""); tot++; } } printf("total: %d\n",tot); } }