文章目录
- [POJ 1625](http://poj.org/problem?id=1625)
- [POJ 2778. DNA Sequence](http://poj.org/problem?id=2778)
- [HDU 2457. DNA repair](http://acm.hdu.edu.cn/showproblem.php?pid=2457)
- [HDU 2825. Wireless Password](http://acm.hdu.edu.cn/showproblem.php?pid=2825)
- [HDU 4057. Rescue the Rabbit](http://acm.hdu.edu.cn/showproblem.php?pid=4057)
- [HDU 3962. Microgene](http://acm.hdu.edu.cn/showproblem.php?pid=3962)
- [HDU 2243. 考研路茫茫 —— 单词情结](http://acm.hdu.edu.cn/showproblem.php?pid=2243)
- [Hdu 4117 GRE Words](http://acm.hdu.edu.cn/showproblem.php?pid=4117)
- [Hdu 3341 Lost's revenge](http://acm.hdu.edu.cn/showproblem.php?pid=3341)
- [bzoj 2434 阿狸的打字机 ](https://www.lydsy.com/JudgeOnline/problem.php?id=2434)
- [Hdu 3247 Resource Archiver](http://acm.hdu.edu.cn/showproblem.php?pid=3247)
POJ 1625
题意：给出包含n个字符的字符集，以下所提字符串均由该字符集中的字符构成。给出p个长度不超过10的字符串，求长为m且不包含上述p个字符串的字符串有多少个。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct NUM{
int t,a[103];
}ans,f[53][103];
struct node{
int las,fail,p[52],v;
}T[103];
int n,m,k,i,j,c,sum,q[1003],t;
char s[53],s1[53];
int get(char ch){
for (int i=0;i<n;i++)
if (s1[i]==ch) return i;
}
void insert(char *s){
int k=0;
for (int i=0;s[i];i++){
int ch=get(s[i]);
if (!T[k].p[ch]) T[k].p[ch]=++sum;
k=T[k].p[ch];
}
T[k].v=1;
}
void build_ac(){
int h=0,t=1;
q[0]=0;
while (h<t){
int u=q[h++];
for (int i=0;i<n;i++){
int v=T[u].p[i];
if (v){
int k=T[u].fail;
while (k && !T[k].p[i]) k=T[k].fail;
k=T[k].p[i];
if (u) T[v].fail=k,T[v].las=T[k].v?k:T[k].las;
q[t++]=v;
}else T[u].p[i]=T[T[u].fail].p[i];
}
}
}
int query(int x,int y){
int tot=0;
for (int i=0;i<n;i++)
if (T[x].p[i]==y) tot++;
return tot;
}
NUM operator +(NUM x,NUM y){
NUM z;
z.t=max(x.t,y.t);
memset(z.a,0,sizeof(z.a));
for (int i=0;i<z.t;i++){
if (i<x.t) z.a[i]+=x.a[i];
if (i<y.t) z.a[i]+=y.a[i];
z.a[i+1]+=z.a[i]/10,z.a[i]%=10;
}
if (z.a[z.t]) z.t++;
return z;
}
void print(NUM x){
if (x.t) for (int i=x.t-1;i>=0;i--) printf("%d",x.a[i]);
else printf("0");
putchar('\n');
}
int main(){
scanf("%d%d%d%s",&n,&m,&k,s1);
for (i=1;i<=k;i++) scanf("%s",s),insert(s);
build_ac();
f[0][0].t=f[0][0].a[0]=1;
for (i=1;i<=m;i++)
for (j=0;j<=sum;j++)
if (!T[j].v && !T[T[j].las].v)
for (k=0;k<=sum;k++)
if (!T[k].v && !T[T[k].las].v)
for (c=0,t=query(k,j);c<t;c++) f[i][j]=f[i][j]+f[i-1][k];
for (i=0;i<=sum;i++) ans=ans+f[m][i];
print(ans);
}
POJ 2778. DNA Sequence
题意：给m个病毒串，问不包含病毒串的长度n的DN***段有几个。
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int M=100000;
struct ma{
ll a[102][102];
}A,B;
struct kk{
int fail,v,p[4];
}T[103];
int ans,i,j,sum,v,n,m,mp[130],q[103];
char s[12];
ma operator *(ma x,ma y){
ma z;
memset(z.a,0,sizeof(z.a));
for (int i=0;i<=sum;i++)
for (int j=0;j<=sum;j++)
for (int k=0;k<=sum;k++) z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%M;
return z;
}
void insert(char *s){
int k=0;
for (int i=0;s[i];i++){
int ch=mp[s[i]];
if (!T[k].p[ch]) T[k].p[ch]=++sum;
k=T[k].p[ch];
}
T[k].v=1;
}
void build_ac(){
int h=0,t=1;
q[0]=0;
while (h<t){
int u=q[h++];
for (int i=0;i<4;i++){
int v=T[u].p[i];
if (v){
int k=T[u].fail;
while (k && !T[k].p[i]) k=T[k].fail;
k=T[k].p[i];
if (u) T[v].fail=k,T[v].v|=T[k].v;
q[t++]=v;
}else T[u].p[i]=T[T[u].fail].p[i];
}
}
}
int main(){
mp['C']=1;mp['G']=2;mp['T']=3;
scanf("%d%d",&m,&n);
for (i=1;i<=m;i++) scanf("%s",s),insert(s);
build_ac();
for (i=0;i<=sum;i++)
if (!T[i].v)
for (j=0;j<4;j++){
v=T[i].p[j];
if (!T[v].v) A.a[i][v]++;
}
for (i=0;i<=sum;i++) B.a[i][i]=1;
for (;n;n>>=1,A=A*A)
if (n&1) B=B*A;
for (i=0;i<=sum;i++) ans=(ans+B.a[0][i])%M;
printf("%d",ans);
}
HDU 2457. DNA repair
题意：给出一些不合法的模式DNA串，给出一个原串，问最少需要修改多少个字符，使得原串中不包含非法串
#include<cstdio>
#include<cstring>
struct kk{
int fail,v,p[4];
}T[1003];
int mp[130],n,l,f[2][1003],q[1003],sum,i,j,k,mn,cas,x,xx;
char s[1003];
inline int min(int x,int y){
return x<y?x:y;
}
inline void init(int x){
T[x].fail=T[x].v=0;
memset(T[x].p,0,sizeof(T[x].p));
}
inline void insert(char *s){
int k=0;
for (int i=0;s[i];i++){
int ch=mp[s[i]];
if (!T[k].p[ch]) init(++sum),T[k].p[ch]=sum;
k=T[k].p[ch];
}
T[k].v=1;
}
inline void build_ac(){
int h=0,t=1;
q[0]=0;
while (h<t){
int u=q[h++];
for (int i=0;i<4;i++){
int v=T[u].p[i];
if (v){
int k=T[u].fail;
while (k && !T[k].p[i]) k=T[k].fail;
k=T[k].p[i];
if (u) T[v].fail=k,T[v].v|=T[k].v;
q[t++]=v;
}else T[u].p[i]=T[T[u].fail].p[i];
}
}
}
int main(){
mp['C']=1;mp['G']=2;mp['T']=3;
while (~scanf("%d",&n)){
if (!n) return 0;
init(0);sum=0;
for (i=0;i<n;i++) scanf("%s",s),insert(s);
build_ac();
scanf("%s",s);
l=strlen(s);
memset(f[0],63,sizeof(f[0]));
f[0][0]=0;
x=0;xx=1;
for (i=0;i<l;i++,x^=1,xx^=1){
memset(f[xx],63,sizeof(f[xx]));
for (j=0;j<=sum;j++)
if (f[x][j]<1e8)
for (k=0;k<4;k++)
if (!T[T[j].p[k]].v) f[xx][T[j].p[k]]=min(f[xx][T[j].p[k]],f[x][j]+(k!=mp[s[i]]));
}
mn=1e9;
for (i=0;i<=sum;i++) mn=min(mn,f[x][i]);
printf("Case %d: %d\n",++cas,mn<1e8?mn:-1);
}
}
HDU 2825. Wireless Password
题意：问长度n至少包含k个咒语的字符串有多少个
#include<cstdio>
#include<cstring>
using namespace std;
const int M=20090717;
struct kk{
int fail,v,p[26];
}T[103];
int q[103],n,m,p,i,k,x,t,ans,f[27][103][1<<10],sum,j;
char s[13];
void mod(int &x){
if (x>=M) x-=M;
}
int get(int x){
int s=0;
for (;x;x-=x&-x) s++;
return s;
}
void build(int x){
T[x].fail=T[x].v=0;
memset(T[x].p,0,sizeof(T[x].p));
}
void insert(char *s,int x){
int k=0;
for (int i=0;s[i];i++){
int ch=s[i]-'a';
if (!T[k].p[ch]) build(++sum),T[k].p[ch]=sum;
k=T[k].p[ch];
}
T[k].v=1<<x;
}
void build_ac(){
int h=0,t=1;
q[0]=0;
while (h<t){
int u=q[h++];
for (int i=0;i<26;i++){
int v=T[u].p[i];
if (v){
int k=T[u].fail;
while (k && !T[k].p[i]) k=T[k].fail;
k=T[k].p[i];
if (u) T[v].fail=k,T[v].v|=T[k].v;
q[t++]=v;
}else T[u].p[i]=T[T[u].fail].p[i];
}
}
}
int main(){
while (1){
scanf("%d%d%d",&n,&m,&p);
if (!n && !m && !p) return 0;
sum=0;
build(0);
for (i=0;i<m;i++) scanf("%s",s),insert(s,i);
build_ac();
memset(f,0,sizeof(f));
f[0][0][0]=1;
for (i=0;i<n;i++)
for (j=0;j<=sum;j++)
for (k=0;k<(1<<m);k++)
if (f[i][j][k])
for (t=0;t<26;t++){
x=T[j].p[t];
mod(f[i+1][x][k|T[x].v]+=f[i][j][k]);
}
ans=0;
for (i=0;i<=sum;i++)
for (j=0;j<(1<<m);j++)
if (get(j)>=p) mod(ans+=f[n][i][j]);
printf("%d\n",ans);
}
}
HDU 4057. Rescue the Rabbit
题意：有ATCG4个字母，要求构成一个长度为l的字符串，给出n个模式串及其权值，问能构成的字符串中最大的权值和是多少，每个模式串只计算一次
#include<cstdio>
#include<cstring>
using namespace std;
struct kk{
int fail,v,p[4],num;
}T[1003];
int q[1003],n,m,p,i,k,x,t,ans,f[2][1003][1<<11],sum,j,mp[130],C,tmp,ne,x1,x2;
char s[103];
void mx(int &x,int y){
if (y>x) x=y;
}
void build(int x){
T[x].fail=T[x].v=T[x].num=0;
memset(T[x].p,0,sizeof(T[x].p));
}
void insert(char *s,int x,int y){
int k=0;
for (int i=0;s[i];i++){
int ch=mp[s[i]];
if (!T[k].p[ch]) build(++sum),T[k].p[ch]=sum;
k=T[k].p[ch];
}
T[k].v|=1<<x;
T[k].num+=y;
}
void build_ac(){
int h=0,t=1;
q[0]=0;
while (h<t){
int u=q[h++];
for (int i=0;i<4;i++){
int v=T[u].p[i];
if (v){
if (u) T[v].fail=T[T[u].fail].p[i];
q[t++]=v;
}else T[u].p[i]=T[T[u].fail].p[i];
}
}
}
int main(){
mp['C']=1;mp['G']=2;mp['T']=3;
while (~scanf("%d%d",&m,&n)){
sum=0;build(0);
for (i=0;i<m;i++) scanf("%s%d",s,&x),insert(s,i,x);
build_ac();
memset(f[0],-63,sizeof(f[0]));
f[0][0][0]=0;
x1=0;x2=1;
for (i=0;i<n;i++,x1^=1,x2^=1){
memset(f[x2],-63,sizeof(f[x2]));
for (j=0;j<=sum;j++)
for (k=0;k<(1<<m);k++)
if (f[x1][j][k]>-1e9)
for (t=0;t<4;t++){
ne=x=T[j].p[t];C=tmp=0;
while (x){
C|=T[x].v;
if (!(k&T[x].v)) tmp+=T[x].num;
x=T[x].fail;
}
mx(f[x2][ne][k|C],f[x1][j][k]+tmp);
}
}
ans=-1e9;
for (i=0;i<=sum;i++)
for (j=0;j<(1<<m);j++) mx(ans,f[x1][i][j]);
if (ans>=0) printf("%d\n",ans);
else printf("No Rabbit after 2012!\n");
}
}
HDU 3962. Microgene
题意：给定m个DNA病毒序列，求碱基构成的长度为n且含有两个以上DNA病毒序列,结果对10007取模。
#include<cstdio>
#include<cstring>
using namespace std;
const int P=10007;
int mp[130],sum,n,m,i,k,j,ans,x,size,q[33];
char s[7];
struct node{
int fail,p[4],v;
}T[33];
struct M{
int a[63][63];
}A;
M operator *(M A,M B){
M C;
memset(C.a,0,sizeof(C.a));
for (int i=0;i<size;i++)
for (int j=0;j<size;j++)
for (int k=0;k<size;k++) C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%P;
return C;
}
M operator ^(M A,int n){
M E;
memset(E.a,0,sizeof(E.a));
for (int i=0;i<size;i++) E.a[i][i]=1;
for (;n;n>>=1,A=A*A)
if (n&1) E=E*A;
return E;
}
void init(int x){
T[x].fail=T[x].v=0;
memset(T[x].p,0,sizeof(T[x].p));
}
void insert(char *s){
int k=0;
for (int i=0;s[i];i++){
int ch=mp[s[i]];
if (!T[k].p[ch]) init(++sum),T[k].p[ch]=sum;
k=T[k].p[ch];
}
T[k].v=1;
}
void build_ac(){
int h=0,t=1;
q[0]=0;
while (h<t){
int u=q[h++];
for (int i=0;i<4;i++){
int v=T[u].p[i];
if (v){
k=T[T[u].fail].p[i];
if (u) T[v].fail=k,T[v].v|=T[k].v;
q[t++]=v;
}else T[u].p[i]=T[T[u].fail].p[i];
}
}
}
int main(){
mp['C']=1;mp['G']=2;mp['T']=3;
while (~scanf("%d%d",&n,&m)){
init(sum=0);
for (i=0;i<n;i++) scanf("%s",s),insert(s);
build_ac();
sum++;
memset(A.a,0,sizeof(A.a));
for (i=0;i<sum;i++)
for (j=0;j<4;j++){
k=T[i].p[j];
if (T[k].v) A.a[i][k+sum]++;
else A.a[i][k]++,A.a[i+sum][k+sum]++;
}
size=sum<<1;A=A^m;ans=1;
for (x=4;m;m>>=1,x=x*x%P)
if (m&1) ans=ans*x%P;
for (i=0;i<size;i++) ans=(ans-A.a[0][i])%P;
printf("%d\n",(ans+P)%P);
}
}
HDU 2243. 考研路茫茫 —— 单词情结
题意：问长度为1~N的串中包含了模式串的串总共有几个。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef unsigned __int64 ll;
int sum,n,m,i,k,j,l,l1;
ll all,left;
char s[9];
struct node{
node *fail,*p[26],*jump[26];
int v;
}rt[53];
queue<node*>q;
struct M{
ll a[53][53];
void clear(){memset(a,0,sizeof(a));}
}A,B,e;
M operator *(M A,M B){
M C;
C.clear();
for (int i=0;i<sum;i++)
for (int j=0;j<sum;j++)
for (int k=0;k<sum;k++) C.a[i][j]+=A.a[i][k]*B.a[k][j];
return C;
}
M operator ^(M A,int n){
M E=e;
for (;n;n/=2,A=A*A)
if (n&1) E=E*A;
return E;
}
void insert(char *s){
node *k=rt;
for (int i=0;s[i];i++){
int ch=s[i]-'a';
if (!k->p[ch]){
k->p[ch]=rt+sum;
memset(rt+sum,0,sizeof(struct node));
sum++;
}
k=k->p[ch];
}
k->v=1;
}
void build_ac(){
q.push(rt);
rt->fail=NULL;
while (!q.empty()){
node *u=q.front();q.pop();
for (int i=0;i<26;i++){
node *k=u->fail,*v=u->p[i];
while (k && !k->p[i]) k=k->fail;
if (v){
if (!k) v->fail=rt;
else v->fail=k->p[i],v->v|=k->p[i]->v;
q.push(v);
u->jump[i]=v;
}else{
if (!k) u->jump[i]=rt;
else u->jump[i]=k->p[i];
}
}
}
}
int main(){
for (i=0;i<52;i++) e.a[i][i]=1;
while (scanf("%d%d",&n,&m)==2){
sum=1;memset(rt,0,sizeof(struct node));
for (i=0;i<n;i++) scanf("%s",s),insert(s);
build_ac();
A.clear();l=0;
for (i=0;i<sum;i++)
if (!rt[i].v){
l1=0;
for (j=0;j<sum;j++)
if (!rt[j].v){
for (k=0;k<26;k++)
if (rt[j].jump[k]==rt+i) A.a[l][l1]++;
l1++;
}
l++;
}
sum=l*2;
for (i=0;i<l;i++) A.a[i][i+l]=A.a[i+l][i+l]=1;
m++;A=A^m;
left=0;
for (i=0;i<l;i++) left+=A.a[i][l];
B.a[0][0]=26;B.a[0][1]=B.a[1][1]=1;B.a[1][0]=0;
sum=2;B=B^m;
all=B.a[0][1]-1;
left--;all-=left;
printf("%I64u\n",all);
}
}
Hdu 4117 GRE Words
题意：给定n个字符串，要求按顺序取一些字符串，满足后一个字符串是前一个字符串的子串，要求使得取出的权值和最大
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define mid (l+r>>1)
#define M(a) memset(a,0,sizeof(a))
const int N=300003,M=20003;
struct kk{
int to,ne;
}e[N];
int p[N][26],fail[N],T,n,sum,tim,i,j,ans,tmp,le[N],ri[N],h[N],tot,tr[N<<2],w[M],now,cas,tag[N<<2];
queue<int>q;
char s1[N];
string s[M];
inline void init(int x){
M(p[x]);fail[x]=0;
}
inline void insert(char *s){
int k=0;
for (int i=0;s[i];i++){
int ch=s[i]-'a';
if (!p[k][ch]) init(++sum),p[k][ch]=sum;
k=p[k][ch];
}
}
inline void build_ac(){
q.push(0);
while (!q.empty()){
int u=q.front();q.pop();
for (int i=0;i<26;i++){
int v=p[u][i];
if (v){
if (u) fail[v]=p[fail[u]][i];
q.push(v);
}else p[u][i]=p[fail[u]][i];
}
}
}
inline void addedge(int x,int y){
e[++tot]=(kk){y,h[x]};
h[x]=tot;
}
inline void dfs(int u){
le[u]=++tim;
for (int i=h[u];i;i=e[i].ne) dfs(e[i].to);
ri[u]=tim;
}
inline void down(int t){
if (tag[t]){
tr[t<<1]=max(tr[t<<1],tag[t]);
tr[t<<1|1]=max(tr[t<<1|1],tag[t]);
tag[t<<1]=max(tag[t<<1],tag[t]);
tag[t<<1|1]=max(tag[t<<1|1],tag[t]);
tag[t]=0;
}
}
inline int query(int t,int l,int r,int x){
if (l==r) return tr[t];
down(t);
if (x<=mid) return query(t<<1,l,mid,x);
return query(t<<1|1,mid+1,r,x);
}
inline void update(int t,int l,int r,int x,int y,int val){
if (x<=l && r<=y){
tr[t]=max(tr[t],val);
tag[t]=max(tag[t],val);
return;
}
down(t);
if (x<=mid) update(t<<1,l,mid,x,y,val);
if (mid<y) update(t<<1|1,mid+1,r,x,y,val);
tr[t]=max(tr[t<<1],tr[t<<1|1]);
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
init(sum=0);
ans=tim=tot=0;
M(h);M(tr);M(tag);
for (i=0;i<n;i++){
scanf("%s%d",s1,&w[i]);
s[i].clear();
for (j=0;s1[j];j++) s[i]+=s1[j];
insert(s1);
}
build_ac();
for (i=1;i<=sum;i++) addedge(fail[i],i);
dfs(0);
for (i=0;i<n;i++){
tmp=now=0;
for (j=0;s[i][j];j++){
now=p[now][s[i][j]-'a'];
tmp=max(tmp,query(1,1,tim,le[now]));
}
tmp+=w[i];
update(1,1,tim,le[now],ri[now],tmp);
ans=max(ans,tmp);
}
printf("Case #%d: %d\n",++cas,ans);
}
}
Hdu 3341 Lost’s revenge
题解
题意：给你多个模板串,然后在给你一个文本串.所有串均只由A,C,G,T,4个字母构成,问你文本串的字符重新排序后最多能有多少个模板串.
#include<bits/stdc++.h>
using namespace std;
struct node{
int mark,fail,ne[5];
}T[503];
int Case,mp[128],k[5],a[5],i,j,l,now,ans,len,n,f[503][15003],sum,v[5];
char s[203];
queue<int>q;
void init(int x){
T[x].mark=0;
memset(T[x].ne,0,sizeof(T[x].ne));
}
void insert(char *s){
int k=0;
for (int i=0;s[i];i++){
int ch=mp[s[i]];
if (!T[k].ne[ch]) init(++sum),T[k].ne[ch]=sum;
k=T[k].ne[ch];
}
T[k].mark++;
}
void build(){
q.push(0);
while (!q.empty()){
int u=q.front();q.pop();
for (int i=1;i<=4;i++)
if (T[u].ne[i]){
T[T[u].ne[i]].fail=u?T[T[u].fail].ne[i]:0;
q.push(T[u].ne[i]);
}else T[u].ne[i]=T[T[u].fail].ne[i];
T[u].mark+=T[T[u].fail].mark;
}
}
int main(){
mp['A']=1;mp['C']=2;mp['G']=3;mp['T']=4;
while (1){
scanf("%d",&n);
if (!n) break;
init(sum=0);
for (i=1;i<=n;i++) scanf("%s",s),insert(s);
build();
scanf("%s",s+1);
len=strlen(s+1);
memset(v,0,sizeof(v));
for (i=1;i<=len;i++) v[mp[s[i]]]++;
k[4]=1;
k[3]=v[4]+1;
k[2]=k[3]*(v[3]+1);
k[1]=k[2]*(v[2]+1);
memset(f,-1,sizeof(f));
f[0][0]=0;ans=0;
for (l=0;l<=len;l++)
for (i=0;i<=sum;i++)
for (a[1]=max(l-v[2]-v[3]-v[4],0);a[1]<=min(l,v[1]);a[1]++)
for (a[2]=max(l-a[1]-v[3]-v[4],0);a[2]<=min(l,v[2]);a[2]++)
for (a[3]=max(l-a[1]-a[2]-v[4],0);a[3]<=min(l,v[3]);a[3]++){
a[4]=l-a[1]-a[2]-a[3];
now=a[1]*k[1]+a[2]*k[2]+a[3]*k[3]+a[4];
if (f[i][now]>=0)
for (j=1;j<=4;j++)
if (a[j]<v[j]){
f[T[i].ne[j]][now+k[j]]=max(f[T[i].ne[j]][now+k[j]],f[i][now]+T[T[i].ne[j]].mark);
ans=max(ans,f[T[i].ne[j]][now+k[j]]);
}
}
printf("Case %d: %d\n",++Case,ans);
}
}
bzoj 2434 阿狸的打字机
#include<bits/stdc++.h>
using namespace std;
const int N=100003;
struct kk{
int p[26],fail;
}T[N];
struct node{
int to,ne;
}e[N];
vector<int>G[N],w[N];
char s[N];
int fa[N],in[N],out[N],dfn,tot,sum,h[N],i,x,y,n,tr[N],pos[N],q[N],ans[N];
int query(int x){
int s=0;
for (;x;x-=x&-x) s+=tr[x];
return s;
}
void add(int x,int y){
for (;x<=dfn;x+=x&-x) tr[x]+=y;
}
void build(){
int u=0,id=0;
for (int i=0;s[i];i++){
if (s[i]=='B') u=fa[u];
else if (s[i]=='P') pos[++id]=u;
else{
int ch=s[i]-'a';
if (!T[u].p[ch]) T[u].p[ch]=++sum,fa[sum]=u;
u=T[u].p[ch];
}
}
}
void build_ac(){
int h=0,t=1;
q[0]=0;
while (h<t){
int u=q[h++];
for (int i=0;i<26;i++){
int &v=T[u].p[i],ch=T[T[u].fail].p[i];
if (v){
q[t++]=v;
if (u) T[v].fail=ch;
}else v=ch;
}
}
}
void solve(){
int u=0,id=0;
for (int i=0;s[i];i++){
if (s[i]=='B') add(in[u],-1),u=fa[u];
else if (s[i]=='P'){
id++;
for (int j=0;j<G[id].size();j++){
int v=pos[G[id][j]];
ans[w[id][j]]=query(out[v])-query(in[v]-1);
}
}else u=T[u].p[s[i]-'a'],add(in[u],1);
}
}
void addedge(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
void dfs(int u){
in[u]=++dfn;
for (int i=h[u];i;i=e[i].ne) dfs(e[i].to);
out[u]=dfn;
}
int main(){
scanf("%s%d",s,&n);
build();
build_ac();
for (i=1;i<=sum;i++) addedge(T[i].fail,i);
for (i=1;i<=n;i++){
scanf("%d%d",&x,&y);
G[y].push_back(x);
w[y].push_back(i);
}
dfs(0);
solve();
for (i=1;i<=n;i++) printf("%d\n",ans[i]);
}
Hdu 3247 Resource Archiver
题解
题意：给n个01串和m个病毒串，要求用01串拼出最短的不包含病毒串的串，输出最短的长度
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=60003,M=203;
struct node{
int ne[2],fail,end;
bool vir;
}T[N];
char s[1003];
int pos[M],d[N],G[M][M],sum,cnt,dp[1<<11][M],n,m,i;
queue<int>q;
void init(int x){
T[x].ne[0]=T[x].ne[1]=T[x].end=T[x].vir=T[x].fail=0;
}
void insert(char *s,int x){
int k=0;
for (int i=0;s[i];i++){
int ch=s[i]^48;
if (!T[k].ne[ch]) init(++sum),T[k].ne[ch]=sum;
k=T[k].ne[ch];
}
if (x>=0) T[k].end=1<<x;
else T[k].vir=1;
}
void build(){
q.push(0);
while (!q.empty()){
int u=q.front();q.pop();
for (int i=0;i<2;i++)
if (T[u].ne[i]){
int v=T[u].ne[i];
if (u) T[v].fail=T[T[u].fail].ne[i];
T[v].end|=T[T[v].fail].end;
T[v].vir|=T[T[v].fail].vir;
q.push(v);
}else T[u].ne[i]=T[T[u].fail].ne[i];
}
}
void path(int k){
memset(d,63,sizeof(d));
q.push(pos[k]);
d[pos[k]]=0;
while (!q.empty()){
int u=q.front();q.pop();
for (int i=0;i<2;i++){
int v=T[u].ne[i];
if (d[v]>1e9 && !T[v].vir) d[v]=d[u]+1,q.push(v);
}
}
for (int i=0;i<cnt;i++) G[k][i]=d[pos[i]];
}
void solve(int n){
memset(dp,63,sizeof(dp));
dp[0][0]=0;
for (int i=0;i<(1<<n);i++)
for (int j=0;j<cnt;j++)
if (dp[i][j]<1e9)
for (int k=0;k<cnt;k++)
if (G[j][k]<1e9){
int t=i|T[pos[k]].end;
dp[t][k]=min(dp[t][k],dp[i][j]+G[j][k]);
}
int ans=1e9,t=(1<<n)-1;
for (int i=0;i<cnt;i++) ans=min(ans,dp[t][i]);
printf("%d\n",ans);
}
int main(){
while (~scanf("%d%d",&n,&m)){
if (!n && !m) break;
init(sum=0);
for (i=0;i<n;i++) scanf("%s",s),insert(s,i);
while (m--) scanf("%s",s),insert(s,-1);
build();
cnt=1;pos[0]=0;
for (i=0;i<=sum;i++)
if (T[i].end) pos[cnt++]=i;
for (i=0;i<cnt;i++) path(i);
solve(n);
}
}
京公网安备 11010502036488号