多模式串匹配，在给出的字符串中查找出现了几个模板串。允许模板串重复，某一个模板串是另一个的前缀或后缀。
http://acm.hdu.edu.cn/showproblem.php?pid=2222
#include <cstdio> #include <cstring> #include <queue> #define maxnode 550000 #define SIGMA_SIZE 26 #define maxlen 1100000 using namespace std; struct AhoCorasickAutomata{ int ch [maxnode][SIGMA_SIZE]; int val[maxnode],last[maxnode],f[maxnode]; int size,cnt; AhoCorasickAutomata() {size=1;memset(ch[0],0,sizeof(ch[0]));} void init() {size=1;memset(ch[0],0,sizeof(ch[0]));} int idx(char c) {return c-'a';}; int BuildNewNode() { memset(ch[size],0,sizeof(ch[size])); val[size]=0;f[size]=0; return size++; } int insert(char *s) { int u=0; for(;*s;s++){ int c=idx(*s); if(!ch[u][c]) ch[u][c]=BuildNewNode(); u=ch[u][c]; } val[u]++; return 0; } int count(int j) { int res=0; while(j){ res+=val[j]; val[j]=0; j=last[j]; } return res; } int find(char *T) { int j=0;cnt=0; for(;*T;T++){ j=ch[j][idx(*T)]; if(val[j]||last[j]) cnt+=count(j); } return cnt; } int getFail() { //init 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; } } //BFS to calculate Fial Array while(!Q.empty()){ int r=Q.front();Q.pop(); for(int c=0;c<SIGMA_SIZE;c++){ int u=ch[r][c],v=f[r]; if(!u){ch[r][c]=ch[f[r]][c];continue;} Q.push(u); while((v)&&(!ch[v][c]))v=f[v]; f[u]=ch[v][c]; last[u]=val[f[u]]?f[u]:last[f[u]]; } } return 0; } }; AhoCorasickAutomata ACmata; char Text[maxlen],keyword[64]; int T,n; int main() { scanf("%d",&T); while(T--){ scanf("%d",&n);getchar(); ACmata.init(); for(int i=0;i<n;i++){ gets(keyword); ACmata.insert(keyword); } ACmata.getFail(); gets(Text); int ans=ACmata.find(Text); printf("%d ",ans); } return 0; }
UVA-11468 - Substring 记得调用idx(),忘了导致WA了无数次。。。。
#include <cstdio> #include <cstring> #include <queue> #define maxnode 2000 #define SIGMA_SIZE 62 #define maxlen 110 using namespace std; char keyword[64]; int T,n,m; double P[SIGMA_SIZE]; double d[maxnode][maxlen]; bool vis[maxnode][maxlen]; struct AhoCorasickAutomata{ int ch [maxnode][SIGMA_SIZE]; int match[maxnode],f[maxnode]; //用match 来记录一个点能不能沿着失败指针走到一个禁点（单词结尾点） //我不需要知道上个单词是谁，也不用知道这个单词是不是结尾，我只想记录能不能到禁点 int size,cnt; AhoCorasickAutomata() {size=1;memset(ch[0],0,sizeof(ch[0]));} void init() {size=1;memset(ch[0],0,sizeof(ch[0]));} int idx(char c) { if('a'<=c && c<='z') return c-'a'; if('A'<=c && c<='Z') return c-'A'+26; if('0'<=c && c<='9') return c-'0'+52; return -1; }; int BuildNewNode() { memset(ch[size],0,sizeof(ch[size])); match[size]=0;f[size]=0; return size++; } int insert(char *s) { int u=0; for(;*s;s++){ int c=idx(*s); if(!ch[u][c]) ch[u][c]=BuildNewNode(); u=ch[u][c]; } match[u]=1; return 0; } int getFail() { //init 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); } } //BFS to calculate Fial Array while(!Q.empty()){ int r=Q.front();Q.pop(); for(int c=0;c<SIGMA_SIZE;c++){ int u=ch[r][c],v=f[r]; if(!u){ch[r][c]=ch[f[r]][c];continue;} Q.push(u); while((v)&&(!ch[v][c]))v=f[v]; f[u]=ch[v][c]; match[u]|=match[f[u]]; } } return 0; } double dfs(int u,int l){ if (!l) return 1.0; if (vis[u][l]) return d[u][l]; vis[u][l]=1;d[u][l]=0; double &ans=d[u][l]; for(int i=0;i<SIGMA_SIZE;i++){ if(!match[ch[u][i]]) ans+=P[i]*dfs(ch[u][i],l-1); } return ans; } }; AhoCorasickAutomata ACmata; int main() { scanf("%d",&T); for(int CaseNum=1;CaseNum<=T;CaseNum++){ memset(vis,0,sizeof(vis)); scanf("%d",&n); for(int i=0;i<SIGMA_SIZE;i++) P[i]=0; ACmata.init(); for(int i=0;i<n;i++){ scanf("%s",keyword); ACmata.insert(keyword); } ACmata.getFail(); scanf("%d",&m); for(int i=0;i<m;i++){ char t; double w; scanf("%s%lf",keyword,&w); //printf("%c %lf ",t,w); P[ACmata.idx(keyword[0])]=w; } int L; scanf("%d",&L); double ans = ACmata.dfs(0,L); printf("Case #%d: %.6lf ",CaseNum,ans); } return 0; }
发现一个不错的模板
http://www.cnblogs.com/arbitrary/archive/2013/03/23/2977134.html
// File Name: 11468.cpp // Author: zlbing // Created Time: 2013/3/21 21:26:32 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define CL(x,v); memset(x,v,sizeof(x)); #define INF 0x3f3f3f3f #define LL long long #define REP(i,r,n) for(int i=r;i<=n;i++) #define RREP(i,n,r) for(int i=n;i>=r;i--) const int SIGMA_SIZE = 65; const int MAXNODE = 1000; const int MAXS = 150 + 10; //map<string,int> ms; //ms是为了满足特殊要求,比如模板串相同时 struct ACautomata { int ch[MAXNODE][SIGMA_SIZE]; int f[MAXNODE]; // fail函数 int val[MAXNODE]; // 每个字符串的结尾结点都有一个非0的val int last[MAXNODE]; // 输出链表的下一个结点 int cnt[MAXS]; int sz; void init() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); memset(cnt, 0, sizeof(cnt)); // ms.clear(); } // 字符c的编号 int idx(char c) { if(c>='0'&&c<='9')return c-'0'; else if(c>='A'&&c<='Z')return c-'A'+10; else if(c>='a'&&c<='z')return c-'a'+36; } // 插入字符串。v必须非0 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]) { memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } val[u] =1; //ms[string(s)] = v; } // 递归打印匹配文本串str[i]结尾的后缀,以结点j结尾的所有字符串 void print(int i,int j) { if(j) { cnt[val[j]]++; print(i,last[j]); } } // 在T中找模板 int 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(i,j); else if(last[j]) print(i,last[j]); // 找到了！ } } // 计算fail函数 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; } } // 按BFS顺序计算fail 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]]; val[u]|=val[f[u]];//计算禁止结点 } } } }; int L; ACautomata solver; double d[MAXNODE][105]; bool vis[MAXNODE][105]; double prob[65]; double dfs(int u,int k){ if(!k)return 1.0; if(vis[u][k])return d[u][k]; double &ans=d[u][k]; ans=0; vis[u][k]=1; for(int i=0;i<SIGMA_SIZE;i++) { if(!solver.val[solver.ch[u][i]]) ans+=prob[i]*dfs(solver.ch[u][i],k-1); } return ans; } int main(){ int T; scanf("%d",&T); int cas=0; while(T--) { char str[30]; int k; solver.init(); scanf("%d",&k); REP(i,1,k) { scanf("%s",&str); solver.insert(str,i); } solver.getFail(); CL(vis,0); scanf("%d",&k); double a; REP(i,0,64)prob[i]=0; REP(i,1,k){ scanf("%s%lf",str,&a); prob[solver.idx(str[0])]=a; } int L; scanf("%d",&L); printf("Case #%d: %.6lf ",++cas,dfs(0,L)); } return 0; }