HDU 3689, UVA 11468 (一)

AC自动机+概率dp

HDU 3689

[cpp]
#include
#include
#include
#include
#include
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;
queueq;
q.push(0);
while(!q.empty()){
int u=q.front();
q.pop();
for(i=0;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 if(fabs(dp[i-1][j])<1e-8)continue;
for(p=0;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
#include
#include
#include
#include
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;
queueq;
q.push(0);
while(!q.empty()){
int u=q.front();
q.pop();
for(i=0;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 if(fabs(dp[i-1][j])<1e-8)continue;
for(p=0;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();