VIJOS1569——AC自动机DP【宋壬初吧】

宋壬初吧关注：25贴子：419

3回复贴，共1页

VIJOS1569——AC自动机DP

var i,j,l,m,n,p,q,t,pre,now,head,tail:longint;
    trie:array[0..200000,'A'..'Z'] of longint;
    father,next,num,queue:array[0..200000] of longint;
    c:array[0..200000] of char;
    dg:array[0..200000] of boolean;
    dp:array[0..2,0..100000] of double;
    win:array[0..100000] of double;
    pb:array['A'..'Z',1..2] of double;
    s:string;
    ch,en,mmm:char;
    sum:double;
procedure ins_trie(s:string);
var g,t:longint;
begin
    t:=0;
    for g:=1 to l do
    begin
        if trie[t,s[g]]>0 then t:=trie[t,s[g]] else
        begin
            inc(p);trie[t,s[g]]:=p;
            father[p]:=t;
            t:=p;c[p]:=s[g];
        end;
    end;
    dg[t]:=true;
    num[t]:=i;
end;
begin
    fillchar(win,sizeof(win),0);
    readln(n,l,m);
    en:=chr(ord('A')+m-1);
    for i:=1 to m do
    begin
        readln(p,q);
        ch:=chr(i+ord('A')-1);
        pb[ch,1]:=p;pb[ch,2]:=q;
    end;
    p:=0;
    for i:=1 to n do
    begin
        readln(s);
        ins_trie(s);
    end;

    head:=0;tail:=0;
    for ch:='A' to en do if trie[0,ch]>0 then
    begin
        inc(tail);
        queue[tail]:=trie[0,ch];
        next[queue[tail]]:=0;
    end;
    while head<tail do
    begin
        inc(head);
        for ch:='A' to en do if trie[queue[head],ch]>0 then

送TA礼物

1楼2009-11-03 23:13回复

        begin
            inc(tail);
            queue[tail]:=trie[queue[head],ch];
            mmm:=c[queue[tail]];
            t:=next[father[queue[tail]]];
            while (t>0)and(trie[t,mmm]=0)do t:=next[t];
            if trie[t,mmm]>0 then t:=trie[t,mmm];
            next[queue[tail]]:=t;
        end;
    end;

    dp[2,0]:=1e15;
    for i:=1 to 1000 do
    begin
        now:=2-(i mod 2);
        pre:=3-now;
        fillchar(dp[now],sizeof(dp[now]),0);
        for j:=0 to p do if not dg[j] then
        begin
            for ch:='A' to en do
            begin
                t:=j;
                if trie[t,ch]>0 then t:=trie[t,ch] else
                begin
                    while (t>0) and (trie[t,ch]=0) do t:=next[t];
                    if trie[t,ch]>0 then t:=trie[t,ch] else t:=0;
                end;
                dp[now,t]:=dp[now,t]+dp[pre,j]*pb[ch,1]/pb[ch,2];
            end;
        end;
        for j:=0 to p do if dg[j] then win[num[j]]:=win[num[j]]+dp[now,j];
    end;
    sum:=0;
    for i:=1 to n do sum:=sum+win[i];
    if sum=0 then
    begin
        for i:=1 to n do writeln(0.0:0:2);
    end else
    begin
        for i:=1 to n do writeln(win[i]/sum:0:2);
    end;
end.

2楼2009-11-03 23:13