首页 > 代码库 > ACM 字符串 题目整理
ACM 字符串 题目整理
AC自动机
UVa 11468 Substring
AC自动机+概率DP。
注意要补全不存在的边。
为什么要补全不存在的边呢？补全以后可以直接找到状态的转移，即从所有子节点就可以实现所有状态转移。
#include<iostream>#include<vector>#include<cmath>#include<map>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<queue>#include<string>#define INF 1000000000LL#define ll long long#define maxnode 4000+5#define sigma_size 62using namespace std;struct Tire{ int ch[maxnode][sigma_size+5],end[maxnode],fail[maxnode]; int root,L; int newnode() { memset(ch[L],0,sizeof(ch[L])); end[L++]=0; return L-1; } void init() { L=0; fail[0]=0; end[0]=0; root=newnode(); } int idx(char c) { if(‘a‘<=c&&c<=‘z‘) return c-‘a‘; else if(‘A‘<=c&&c<=‘Z‘) return c-‘A‘+26; else if(‘0‘<=c&&c<=‘9‘) return c-‘0‘+52; } void insert(char* word) { int now=0; for(int i=0; word[i]; ++i) { int x=idx(word[i]); if(!ch[now][x]) ch[now][x]=newnode(); now=ch[now][x]; } end[now]=1; } void build() { queue<int> que; for(int i=0; i<sigma_size; ++i) { if(ch[0][i]) { que.push(ch[0][i]); fail[ch[0][i]]=0; } } while(!que.empty()) { int q=que.front(); que.pop(); for(int i=0; i<sigma_size; ++i) { int u=ch[q][i]; if(!u) { ch[q][i]=ch[fail[q]][i]; continue; } int v=fail[q]; que.push(u); while(v&&!ch[v][i]) v=fail[v]; fail[u]=ch[v][i]; end[u]|=end[fail[u]]; } } }};Tire ac;double pro[sigma_size+5];double f[maxnode+5][105];bool vis[maxnode+5][105];bool cha[sigma_size+5];double dp(int now,int L){ if(!L) return 1.0; if(vis[now][L]) return f[now][L]; vis[now][L]=true; f[now][L]=0.0; for(int i=0; i<sigma_size; ++i) if(cha[i]) { int u=ac.ch[now][i]; if(!ac.end[u]) f[now][L]+=pro[i]*dp(u,L-1); } return f[now][L];}int main(){ int T,kase=0; //freopen("read.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&T); while(T--) { int k; scanf("%d",&k); ac.init(); memset(vis,0,sizeof(vis)); memset(cha,0,sizeof(cha)); for(int i=0; i<k; ++i) { char word[100]; scanf("%s",word); ac.insert(word); } ac.build(); int n; scanf("%d",&n); memset(pro,0,sizeof(pro)); for(int i=0; i<n; ++i) { char word[3]; double p; scanf("%s%lf",word,&p); int q=ac.idx(word[0]); cha[q]=true; pro[q]=p; } int L; scanf("%d",&L); double ans=dp(0,L); printf("Case #%d: %.6lf\n",++kase,ans); } return 0;}
HDU 2825 Wireless Password
AC自动机+状态压缩DP
求长度为n的字符串中包含超过k个模式串的个数。
dp[i][j][k]表示长为i，当前状态为j时的字符串包括k个串时的个数，k为集合。
状态压缩使每个串唯一，而不必考虑重复。串可以重叠而考虑AC自动机。
另外注意如果当前dp为0，那就不用刷表了。
#include<iostream>#include<vector>#include<cmath>#include<map>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<queue>#include<string>#define ll long long#define maxnode 105#define sigma_size 26#define maxn 100#define MOD 20090717using namespace std;int n,m,K;int countBit(int val){ int cnt=0; while(val) { cnt+=val%2; val/=2; } return cnt;}struct Tire{ int ch[maxnode][sigma_size],end[maxnode],fail[maxnode]; int root,L; int newnode() { memset(ch[L],0,sizeof(ch[L])); end[L++]=0; return L-1; } void init() { L=0; fail[0]=0; end[0]=0; root=newnode(); } int idx(char c) { return c-‘a‘; } void insert(char* word,int p) { int now=0; for(int i=0; word[i]; ++i) { int x=idx(word[i]); if(!ch[now][x]) ch[now][x]=newnode(); now=ch[now][x]; } end[now]=1<<p; } void build() { queue<int> que; for(int i=0; i<sigma_size; ++i) { if(ch[0][i]) { que.push(ch[0][i]); fail[ch[0][i]]=0; } } while(!que.empty()) { int q=que.front(); que.pop(); for(int i=0; i<sigma_size; ++i) { int u=ch[q][i]; if(!u) { ch[q][i]=ch[fail[q]][i]; continue; } int v=fail[q]; que.push(u); while(v&&!ch[v][i]) v=fail[v]; fail[u]=ch[v][i]; end[u]|=end[fail[u]]; } } } int dp[27][maxn][(1<<10)+1]; int solve() { memset(dp,0,sizeof(dp)); dp[0][0][0]=1; for(int i=0; i<n; ++i) { for(int j=0; j<L; ++j) { for(int k=0; k<(1<<m); ++k) if(dp[i][j][k]) { for(int l=0; l<26; ++l) { int u=ch[j][l]; int &res=dp[i+1][u][k|end[u]]; res+=dp[i][j][k]; res%=MOD; } } } } int ans=0; for(int j=0; j<(1<<m); ++j) if(countBit(j)>=K) { for(int i=0; i<L; ++i) { ans+=dp[n][i][j]; ans%=MOD; } } return ans; }};Tire ac;int main(){ while(scanf("%d%d%d",&n,&m,&K)!=EOF) { if(!n&&!m&&!K) break; ac.init(); for(int i=0; i<m; ++i) { char word[30]; scanf("%s",word); ac.insert(word,i); } ac.build(); printf("%d\n",ac.solve()); } return 0;}
POJ 3691 DNA repair
AC自动机+DP
问修改最少字符使得串中不含模式子串。
dp[i][j]表示当前是当串中第j个位置是第i个节点状态时的最优解。
当c不是结束节点的时候，c表示从i转移到的状态
dp[i][j]=min{dp[c][j+1]+1}//如果此时需要修改
dp[i][j]=min{dp[c][j+1]}//如果此时不修改
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <vector>#include <queue>#define ll long longusing namespace std;const int maxnode =1005;const int sigma_size=4;const int inf =1000000000;struct Tire{ int ch[maxnode][sigma_size]; int end[maxnode],fail[maxnode]; int sz; int newnode() { memset(ch[sz],0,sizeof(ch[sz])); fail[sz]=0; end[sz++]=0; return sz-1; } void init() { sz=0; newnode(); } int idx(char c) { if(c==‘A‘) return 0; if(c==‘G‘) return 1; if(c==‘C‘) return 2; if(c==‘T‘) return 3; } void insert(char *word) { int now=0; for(int i=0; word[i]; ++i) { int x=idx(word[i]); if(!ch[now][x]) ch[now][x]=newnode(); now=ch[now][x]; } end[now]=1; } void build() { queue<int> que; for(int i=0; i<sigma_size; ++i) { int u=ch[0][i]; if(u) { fail[u]=0; que.push(u); } } while(!que.empty()) { int q=que.front(); que.pop(); for(int i=0; i<sigma_size; ++i) { int u=ch[q][i],v=fail[q]; if(!u) { ch[q][i]=ch[v][i]; continue; } que.push(u); while(v&&!ch[v][i]) v=fail[v]; fail[u]=ch[v][i]; end[u]|=end[fail[u]]; } } }};bool vis[1005][1005];int f[1005][1005];char str[1005];int N;Tire ac;int dp(int now,int L){ if(L==N) return 0; if(vis[now][L]) return f[now][L]; vis[now][L]=true; f[now][L]=inf; for(int i=0; i<4; ++i) { int y=ac.idx(str[L]); int u=ac.ch[now][i]; if(!ac.end[u]) { if(y!=i&&dp(u,L+1)!=inf) f[now][L]=min(f[now][L],dp(u,L+1)+1); else if(y==i&&dp(u,L+1)!=inf) f[now][L]=min(f[now][L],dp(u,L+1)); } } return f[now][L];}int main(){ int n,kase=0; while(scanf("%d",&n)&&n) { char word[30]; ac.init(); memset(vis,0,sizeof(vis)); for(int i=1; i<=n; ++i) { scanf("%s",word); ac.insert(word); } scanf("%s",str); ac.build(); N=strlen(str); printf("Case %d: ",++kase); int ans=dp(0,0); if(ans==inf) puts("-1"); else printf("%d\n",ans); } return 0;}
字典树
POJ 3630 Phone List
问有没有一个电话号是另一个电话号的前缀。
典型的trie树，时间复杂度是10n。注意不要边读入边判断。否则像12、2这样就判不出来。
#include<cstdio>#include<vector>#include<algorithm>#include<queue>#include<cstring>#define LL unsigned intusing namespace std;const int maxnode =1000005;const int sigma_size=12;struct Tire{ int ch[maxnode][sigma_size]; int end[maxnode]; int sz; int newnode() { memset(ch[sz],0,sizeof(ch[sz])); end[sz]=0; return sz++; } void init() { sz=0; newnode(); } bool insert(char *word,int v) { int now=0; for(int i=0; word[i]; ++i) { int x=word[i]-‘0‘; if(!ch[now][x]) ch[now][x]=newnode(); now=ch[now][x]; if(end[now]&&end[now]!=v) return false; } end[now]=v; return true; }};Tire tree;char numb[100005][12];int main(){ int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); bool ok=true; tree.init(); for(int i=1; i<=n; ++i) { scanf("%s",numb[i]); if(ok&&!tree.insert(numb[i],i)) ok=false; } for(int i=1; i<=n&&ok; ++i) { if(!tree.insert(numb[i],i)) ok=false; } if(ok) puts("YES"); else puts("NO"); } return 0;}
POJ 1204 Word Puzzles
在一个字符矩阵中寻找出现的字符串，并输出头字符的位置和方向。
可以用字典树来做。枚举每个位置再枚举方向，这样每次遍历一个字符串看是否出现了模式串。
#include<cstdio>#include<vector>#include<algorithm>#include<queue>#include<cstring>#define LL unsigned intusing namespace std;const int maxnode =1000*1000+5;const int sigma_size=26;char mat[1005][1005];int C,L,W;bool judge(int x,int y){ return 0<=x&&x<L&&0<=y&&y<C;}int ax,ay,d;int ans[1005][3];const int dir[8][2]= {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};struct Tire{ int ch[maxnode][sigma_size]; int end[maxnode]; int sz; int newnode() { memset(ch[sz],-1,sizeof(ch[sz])); end[sz]=0; return sz++; } void init() { sz=0; newnode(); } int idx(char c) { return c-‘A‘; } void insert(char *word,int v) { int now=0; for(int i=0; word[i]; ++i) { int x=idx(word[i]); if(ch[now][x]==-1) ch[now][x]=newnode(); now=ch[now][x]; } end[now]=v; } void find(int x,int y) { int now=0; while(1) { int c=idx(mat[x][y]); now=ch[now][c]; if(now==-1) break; if(end[now]) { ans[end[now]][0]=ax; ans[end[now]][1]=ay; ans[end[now]][2]=d; end[now]=0; } x+=dir[d][0]; y+=dir[d][1]; if(!judge(x,y)) break; } } void find(int x,int y,int now) { if(now==-1 )return; if(end[now]>0) { ans[end[now]][0]=ax; ans[end[now]][1]=ay; ans[end[now]][2]=d; end[now]=0; } if(!judge(x,y)) return; find(x+dir[d][0],y+dir[d][1],ch[now][idx(mat[x][y])]); }};Tire tree;int main(){ while(scanf("%d%d%d",&L,&C,&W)!=EOF) { for(int i=0; i<L; ++i) scanf("%s",mat[i]); tree.init(); for(int i=1; i<=W; ++i) { char str[1005]; scanf("%s",str); tree.insert(str,i); } for(int i=0; i<L; ++i) for(int j=0; j<C; ++j) for(int k=0; k<8; ++k) { ax=i; ay=j; d=k; tree.find(i,j); } for(int i=1; i<=W; ++i) printf("%d %d %c\n",ans[i][0],ans[i][1],ans[i][2]+‘A‘); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。