题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2896
题意:有N(1<=N<=500)个模板串，每个模板串的长度n <= 200;之后有M(1<=M <= 1000)个文本串，每个文本串的长度len <= 10000;问有多少个模板串出现在输入的文本串中，按照模板串的顺序排序输出；
思路:ac自动机裸题。。
坑点:字符的为可行的ASCII码，即sigma_size = 128;并且还是idx好用，之后直接改即可；好几发都是写s[i] - 'a'..醉了
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef pair<int,int> PII; #define A first #define B second #define MK make_pair #define pb push_back typedef __int64 ll; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } int T,kase = 1,i,j,k,n,m; const int sigma_size = 128;//** const int maxn = 200*500+7; struct Aho_Corasick{ int ch[maxn][sigma_size]; int val[maxn],f[maxn],last[maxn],cnt[maxn]; int sz; map<string,int> ms; vector<int> vec; Aho_Corasick(){} void init(){sz = 1; MS0(ch[0]);MS0(cnt);ms.clear();} int idx(char c){return c;} void Insert(char *s,int v){ int u = 0,n = strlen(s); for(int i = 0;i < n;i++){ int c = idx(s[i]); if(!ch[u][c]){ MS0(ch[sz]); val[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } val[u] = v; ms[string(s)] = v; } void getFail(){ queue<int> q; f[0] = 0; //初始化队列 for(int c = 0;c < sigma_size;c++){ int u = ch[0][c]; if(u) { f[u] = 0; q.push(u); last[u] = 0;} } while(!q.empty()){ int r = q.front();q.pop(); for(int c = 0;c < sigma_size;c++){ int u = ch[r][c]; if(!u) {ch[r][c] = ch[f[r]][c]; continue;}//实现压缩 q.push(u); int v = f[r]; while(v && !ch[v][c]) v = f[v]; f[u] = ch[v][c]; last[u] = val[f[u]]?f[u]:last[f[u]]; } } } //从文本串中找模板; void Find(char *T){ int n = strlen(T); int j = 0; for(int i = 0;i < n;i++){ int c = idx(T[i]); j = ch[j][c];//直接查找即可; if(val[j]) print(j); else if(last[j]) print(last[j]); } } void print(int j){ if(j) { vec.pb(val[j]); print(last[j]); } } }ac; char p[255]; char text[10007]; int main() { while(scanf("%d",&n) == 1){ ac.init(); rep1(i,1,n){ scanf("%s",p); ac.Insert(p,i); } ac.getFail(); int tot = 0; read1(m); rep1(k,1,m){ scanf("%s",text); ac.Find(text); int sz = ac.vec.size(); if(sz){ tot++; printf("web %d:",k); sort(ac.vec.begin(),ac.vec.end()); sz = unique(ac.vec.begin(),ac.vec.end())-ac.vec.begin(); rep0(i,0,sz){ putchar(' '); out(ac.vec[i]); } puts(""); } ac.vec.clear(); } printf("total: %d ",tot); } return 0; }