AC自動機+概率dp
HDU 3689
[cpp]
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<math.h>
using namespace std;
int n,nn,m;
int ok[200];
double pp[200];
int next[100][30],fail[100],flag[100],pos;
int newnode(){
int i=0;
for(;i<26;i++)next[pos][i]=0;
fail[pos]=flag[pos]=0;
return pos++;
}
int insert(char * s){
int i,p=0;
for(i=0;s[i];i++){
int k=ok[s[i]];
if(k==-1)return 0;
int &x=next[p][k];
p=x?x:x=newnode();
}
flag[p]=1;
return 1;
}
void makefail(){
int i;
queue<int>q;
q.push(0);
while(!q.empty()){
int u=q.front();
q.pop();
for(i=0;i<nn;i++){
int v=next[u][i];
if(v==0)next[u][i]=next[fail[u]][i];
else q.push(v);
if(u&&v){
fail[v]=next[fail[u]][i];
flag[v]|=flag[fail[v]];
}
}
}
}
double dp[1020][100];
void dps(){
int i,j,k,p;
double ans=0;
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(i=1;i<=m;i++){
for(j=0;j<pos-1;j++){
if(fabs(dp[i-1][j])<1e-8)continue;
for(p=0;p<nn;p++){
int v=next[j][p];
dp[i][v]+=dp[i-1][j]*pp[p];
}
}
}
for(i=1;i<=m;i++)
ans+=dp[i][pos-1];
printf("%.2lf",ans*100);
putchar('%');
putchar('\n');
}
int main(){
int i,k;
char s[100];
double tem;
while(scanf("%d %d",&n,&m)==2){
if(n==0 && m==0)break;
pos=0,newnode();
memset(ok,-1,sizeof(ok));
for(i=0;i<100;i++)pp[i]=0;
k=0;
for(i=1;i<=n;i++){
scanf("%s %lf",s,&tem);
if(ok[s[0]]==-1)
ok[s[0]]=k++;
pp[ok[s[0]]]+=tem;
}
nn=k;
scanf("%s",s);
int len=strlen(s);
if(len>m || insert(s)==0){
printf("0.00");
putchar('%');
putchar('\n');
continue;
}
makefail();
dps();
}
}
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<math.h>
using namespace std;
int n,nn,m;
int ok[200];
double pp[200];
int next[100][30],fail[100],flag[100],pos;
int newnode(){
int i=0;
for(;i<26;i++)next[pos][i]=0;
fail[pos]=flag[pos]=0;
return pos++;
}
int insert(char * s){
int i,p=0;
for(i=0;s[i];i++){
int k=ok[s[i]];
if(k==-1)return 0;
int &x=next[p][k];
p=x?x:x=newnode();
}
flag[p]=1;
return 1;
}
void makefail(){
int i;
queue<int>q;
q.push(0);
while(!q.empty()){
int u=q.front();
q.pop();
for(i=0;i<nn;i++){
int v=next[u][i];
if(v==0)next[u][i]=next[fail[u]][i];
else q.push(v);
if(u&&v){
fail[v]=next[fail[u]][i];
flag[v]|=flag[fail[v]];
}
}
}
}
double dp[1020][100];
void dps(){
int i,j,k,p;
double ans=0;
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(i=1;i<=m;i++){
for(j=0;j<pos-1;j++){
if(fabs(dp[i-1][j])<1e-8)continue;
for(p=0;p<nn;p++){
int v=next[j][p];
dp[i][v]+=dp[i-1][j]*pp[p];
}
}
}
for(i=1;i<=m;i++)
ans+=dp[i][pos-1];
printf("%.2lf",ans*100);
putchar('%');
putchar('\n');
}
int main(){
int i,k;
char s[100];
double tem;
while(scanf("%d %d",&n,&m)==2){
if(n==0 && m==0)break;
pos=0,newnode();
memset(ok,-1,sizeof(ok));
for(i=0;i<100;i++)pp[i]=0;
k=0;
for(i=1;i<=n;i++){
scanf("%s %lf",s,&tem);
if(ok[s[0]]==-1)
ok[s[0]]=k++;
pp[ok[s[0]]]+=tem;
}
nn=k;
scanf("%s",s);
int len=strlen(s);
if(len>m || insert(s)==0){
printf("0.00");
putchar('%');
putchar('\n');
continue;
}
makefail();
dps();
}
}
UVA 11468
[cpp] view plaincopyprint?#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<math.h>
#define N 500
using namespace std;
int nn,m;
int ok[200];
double pp[200];
int next[N][70],fail[N],flag[N],pos;
char s[100];
int newnode(){
int i=0;
memset(next[pos],0,sizeof(next[pos]));
fail[pos]=flag[pos]=0;
return pos++;
}
void insert(char * s){
int i,p=0;
for(i=0;s[i];i++){
int k=ok[s[i]];
int &x=next[p][k];
p=x?x:x=newnode();
}
flag[p]=1;
}
void makefail(){
int i;
queue<int>q;
q.push(0);
while(!q.empty()){
int u=q.front();
q.pop();
for(i=0;i<nn;i++){
int v=next[u][i];
if(v==0)next[u][i]=next[fail[u]][i];
else q.push(v);
if(u&&v){
fail[v]=next[fail[u]][i];
flag[v]|=flag[fail[v]];
}
}
}
}
double dp[110][N];
void dps(){
int i,j,k,p;
double ans=0;
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(i=1;i<=m;i++){
for(j=0;j<pos;j++){
if(flag[j])continue;
for(p=0;p<nn;p++){
int v=next[j][p];
dp[i][v]+=dp[i-1][j]*pp[p];
}
}
}
for(j=0;j<pos;j++)
if(!flag[j])
ans+=dp[m][j];
printf("%lf\n",ans);
}
int main(){
int i,k,n,cou;
char s[25][25],str[10];
double tem;
int t,T;
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%d",&k);
for(i=0;i<k;i++) scanf("%s",s[i]);
memset(ok,-1,sizeof(ok));
for(i=0;i<100;i++)pp[i]=0;
cou=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%s %lf",str,&tem);
if(ok[str[0]]==-1)
ok[str[0]]=cou++;
pp[ok[str[0]]]+=tem;
}
nn=cou;
scanf("%d",&m);
pos=0,newnode();
for(i=0;i<k;i++) insert(s[i]);
makefail();
printf("Case #%d: ",t);
dps();
}
}
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<math.h>
#define N 500
using namespace std;
int nn,m;
int ok[200];
double pp[200];
int next[N][70],fail[N],flag[N],pos;
char s[100];
int newnode(){
int i=0;
memset(next[pos],0,sizeof(next[pos]));
fail[pos]=flag[pos]=0;
return pos++;
}
void insert(char * s){
int i,p=0;
for(i=0;s[i];i++){
int k=ok[s[i]];
int &x=next[p][k];
p=x?x:x=newnode();
}
flag[p]=1;
}
void makefail(){
int i;
queue<int>q;
q.push(0);
while(!q.empty()){
int u=q.front();
q.pop();
for(i=0;i<nn;i++){
int v=next[u][i];
if(v==0)next[u][i]=next[fail[u]][i];
else q.push(v);
if(u&&v){
fail[v]=next[fail[u]][i];
flag[v]|=flag[fail[v]];
}
}
}
}
double dp[110][N];
void dps(){
int i,j,k,p;
double ans=0;
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(i=1;i<=m;i++){
for(j=0;j<pos;j++){
if(flag[j])continue;
for(p=0;p<nn;p++){
int v=next[j][p];
dp[i][v]+=dp[i-1][j]*pp[p];
}
}
}
for(j=0;j<pos;j++)
if(!flag[j])
ans+=dp[m][j];
printf("%lf\n",ans);
}
int main(){
int i,k,n,cou;
char s[25][25],str[10];
double tem;
int t,T;
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%d",&k);
for(i=0;i<k;i++) scanf("%s",s[i]);
memset(ok,-1,sizeof(ok));
for(i=0;i<100;i++)pp[i]=0;
cou=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%s %lf",str,&tem);
if(ok[str[0]]==-1)
ok[str[0]]=cou++;
pp[ok[str[0]]]+=tem;
}
nn=cou;
scanf("%d",&m);
pos=0,newnode();
for(i=0;i<k;i++) insert(s[i]);
makefail();
printf("Case #%d: ",t);
dps();
}
}
