Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1625 Censored!---AC 自动机+DP+高精度

Posted on 2010-10-30 23:40 Uriel 阅读(1269) 评论(0)  编辑 收藏 引用 所属分类: POJDP字符串处理
        第二道AC自动机,对DP状态转移有一点感觉了。。。
        这题基本和2778一样,不过要高精度,所以就想用JAVA试试,正好JAVA很久不碰了,跟没学过一样,Regional之前练习练习,结果做得我痛不欲生。。00:00-03:10,06:50-09:00一直在整JAVA,先是不会用Class,翻书+上网搜+乱搞,终于不报错。。然后发现对象数组初始化又有问题。。然后函数又有问题。。各种纠结之后。。TLE。。方法是构造AC自动机,求状态转移矩阵,然后二分矩阵链乘。。TLE之后乱搞了一下没什么效果。。只好放弃。。
        搜到某大牛Blog说这题矩阵链乘会爆栈,于是没敢写,跟网上大部分代码一样直接DP了(滚动数组),晚上终于AC。。

这是TLE的JAVA代码,不知道怎么改,还是说这种方法过不了,欢迎路过的大牛指教

//Problem: 1625  User: Uriel 
//Memory: N/A  Time: N/A 
//Language: Java  Result: Time Limit Exceeded 

import java.util.*;
import java.math.BigInteger;

class Node{
    
public int fail; 
    
public int nxt[]=new int[51];
    
public int cnt; 
    
public void init()
        
for(int i=0;i<51;++i)nxt[i]=-1;
    }

}


public class Main {
    
static int kind,nnode,n,m,len,head,tail;
    
static char s[]=new char[51];
    
static char word[]=new char[11];
    
static int d[]=new int[260];
    
static int que[]=new int[300];
    
static BigInteger mtx[][]=new BigInteger[300][300];
    
static BigInteger g[][]=new BigInteger[300][300];
    
static Node q[]=new Node[300];
    
static int gg[][]=new int[300][300];
    
public static void insert(){
        
int i,p=0;
        
for(i=0;i<len;++i){
            
if(q[p].nxt[d[s[i]]]==-1){
                nnode
++;
                q[p].nxt[d[s[i]]]
=nnode;
                q[nnode]
=new Node();
                q[nnode].init();
            }
 
            
if (q[p].cnt>0break;
            p
=q[p].nxt[d[s[i]]];
        }

        q[p].cnt
++;
    }


    
public static void build_ac_automation(){
        
int tmp,p,i;
        que[tail
++]=0;
        
while(head<tail){
            tmp
=que[head++];
            
for(i=0;i<kind;++i){
                
if(q[tmp].nxt[i]!=-1){
                    
if(tmp==0)q[q[tmp].nxt[i]].fail=0;
                    
else{
                        p
=q[tmp].fail;
                        
while(p!=-1){
                            
if(q[p].nxt[i]!=-1){
                                q[q[tmp].nxt[i]].fail
=q[p].nxt[i];
                                
if(q[q[p].nxt[i]].cnt>0) q[q[tmp].nxt[i]].cnt++;
                                
break;
                            }

                            p
=q[p].fail;
                        }

                        
if(p==-1)q[q[tmp].nxt[i]].fail=0;
                    }

                    que[tail
++]=q[tmp].nxt[i];
                }

            }

        }

    }


    
public static void build_adj(){
        
int i,j;
        
for(i=0;i<nnode;++i)
            
for(j=0;j<kind;++j)gg[i][j]=0;
        
for(i=0;i<nnode;++i)
            
if(q[i].cnt==0)
                
for(j=0;j<kind;++j){
                    
if(q[i].nxt[j]!=-1 && q[q[i].nxt[j]].cnt==0)gg[i][q[i].nxt[j]]++;
                    
else if(q[i].nxt[j]==-1){
                        
if(i==0)gg[0][0]++;
                        
else{
                            
int tmp=i;
                            
while(q[tmp].nxt[j]==-1){
                                
if(tmp==0)break;
                                tmp
=q[tmp].fail;
                            }

                            
if(q[tmp].nxt[j]!=-1 && q[q[tmp].nxt[j]].cnt==0)gg[i][q[tmp].nxt[j]]++;
                            
else if(q[tmp].nxt[j]==-1 && tmp==0)gg[i][0]++;
                        }

                    }

                }

    }


    
public static void MatrixMul(BigInteger b[][],BigInteger c[][],int sz){
        
int i,j,k;
        BigInteger tmp[][]
=new BigInteger[sz][sz];
        
for(i=0;i<sz;++i)
            
for(j=0;j<sz;++j)
                tmp[i][j]
=BigInteger.ZERO;
        
for(i=0;i<sz;++i)
            
for(j=0;j<sz;++j)
                
for(k=0;k<sz;++k){
                    tmp[i][j]
=tmp[i][j].add(b[i][k].multiply(c[k][j]));
                }

                
for(i=0;i<sz;++i)
                    
for(j=0;j<sz;++j)
                        b[i][j]
=tmp[i][j];
    }


    
public static void MatrixPow(BigInteger mtx[][],BigInteger a[][],int sz,int k){
        
while(k>0){
            
if(k%2==1)MatrixMul(mtx,a,sz);
            MatrixMul(a,a,sz);
            k
>>=1;
        }

    }


    
public static void main(String[] args){
        
int i,j,m,n;
        Scanner stdin
=new Scanner(System.in);
        kind
=stdin.nextInt();
        n
=stdin.nextInt();
        m
=stdin.nextInt();
        String ss
=stdin.next();
        word
=ss.toCharArray();
        len
=ss.length();
        
for(i=0;i<len;++i)d[word[i]]=i;
        head
=tail=0;
        nnode
=0;
        q[
0]=new Node();
        q[
0].init();
        
for(i=0;i<m;++i){
            ss
=stdin.next();
            len
=ss.length();
            s
=ss.toCharArray();
            insert();
        }

        build_ac_automation();
        nnode
++;
        build_adj();
        
for(i=0;i<nnode;++i)
            
for(j=0;j<nnode;++j){
                g[i][j]
=BigInteger.valueOf(gg[i][j]);
                
if(i==j)mtx[i][j]=BigInteger.ONE;
                
else
                    mtx[i][j]
=BigInteger.ZERO;
            }

            MatrixPow(mtx,g,nnode,n);
            BigInteger ans
=BigInteger.ZERO;
            
for(i=0;i<nnode;++i)ans=ans.add(mtx[0][i]);
            System.out.println(ans);
    }

}




下面是AC的C++代码,高精度乘法部分参考了网上某大牛的写法,AC自动机我的模板异常的慢,但是不知道怎么改了。。也希望路过的大牛指教。。

//Problem: 1625  User: Uriel 
//Memory: 496K  Time: 422MS 
//Language: G++  Result: Accepted 

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#define max(x,y) (x>y?x:y)

struct node{
    
int fail;
    
int nxt[51];
    
int cnt;
    
void init(){
        fail
=-1;
        cnt
=0;
        memset(nxt,
-1,sizeof(nxt));
    }

}
q[1010];

struct BigInt{
    
int a[100];
}
f[2][105];

int nnode,n,m,maxl,ans[105];
int head,tail;
int d[300],que[300];

void insert(char *s){
    
int i,p=0;
    
for(i=0;s[i];++i){
        
if(q[p].nxt[d[s[i]]]==-1){
            nnode
++;
            q[p].nxt[d[s[i]]]
=nnode;
            q[nnode].init();
        }
 
        
if(q[p].cnt)break;
        p
=q[p].nxt[d[s[i]]];
    }

    q[p].cnt
++;
}


void build_ac_automation(){
    
int tmp,p,i,j;
    que[tail
++]=0;
    
while(head<tail){
        tmp
=que[head++];
        
for(i=0;i<maxl;++i){
            
if(~q[tmp].nxt[i]){
                
if(!tmp)q[q[tmp].nxt[i]].fail=0;
                
else{
                    p
=q[tmp].fail;
                    
while(~p){
                        
if(~q[p].nxt[i]){
                            q[q[tmp].nxt[i]].fail
=q[p].nxt[i];
                            
if(q[q[p].nxt[i]].cnt) q[q[tmp].nxt[i]].cnt++;
                            
break;
                        }

                        p
=q[p].fail;
                    }

                    
if(p==-1)q[q[tmp].nxt[i]].fail=0;
                }

                que[tail
++]=q[tmp].nxt[i];
            }

        }

    }

}


void add(int a[105],int b[105]){
    
int c[105],i;
    memset(c,
0,sizeof(c));
    
int Len=max(a[0],b[0]);
    
for(i=a[0]+1;i<=Len;i++)a[i]=0;
    
for(i=b[0]+1;i<=Len;i++)b[i]=0;
    
for(i=1;i<=Len;i++){
        c[i]
=c[i-1]/10+a[i]+b[i];
        c[i
-1]=c[i-1]%10;
    }

    c[
0]=Len;
    
while(c[c[0]]>=10){
        c[
0]++;
        c[c[
0]]=c[c[0]-1]/10;
        c[c[
0]-1]=c[c[0]-1%10;
    }

    
for(i=0;i<=c[0];i++)b[i]=c[i];
}


void solve() {
    
int cur=0,i,j;
    
for(i=0;i<nnode;i++{
        
if(!i)f[cur][i].a[0]=f[cur][i].a[1]=1
        
else f[cur][i].a[0]=1,f[cur][i].a[1]=0;
    }

    
while(n--){
        
for(i=0;i<nnode;i++)f[1-cur][i].a[0]=1,f[1-cur][i].a[1]=0;
        
for(i=0;i<nnode;i++){
            
if(q[i].cnt)continue;
            
for(j=0;j<maxl;j++){
                
if(q[i].nxt[j]!=-1 && !q[q[i].nxt[j]].cnt){
                    add(f[cur][i].a,f[
1-cur][q[i].nxt[j]].a);
                }

                
else if(q[i].nxt[j]==-1){
                    
if(!i)add(f[cur][i].a,f[1-cur][0].a);
                    
else{
                        
int tp=i;
                        
while(q[tp].nxt[j]==-1){
                            
if(!tp)break;
                            tp
=q[tp].fail;
                        }

                        
if(~q[tp].nxt[j] && !q[q[tp].nxt[j]].cnt)add(f[cur][i].a,f[1-cur][q[tp].nxt[j]].a);
                        
else if(q[tp].nxt[j]==-1 && tp==0)add(f[cur][i].a,f[1-cur][0].a);
                    }

                }

            }

        }

        cur
=1-cur;
    }

    ans[
0]=1,ans[1]=0;
    
for(i=0;i<nnode;i++)add(f[cur][i].a,ans);
    
for(i=ans[0];i>=1;i--)printf("%d",ans[i]);
    putchar(
10);
}


int main(){
    
int i;
    
char s[110];
    scanf(
"%d %d %d",&maxl,&n,&m);
    scanf(
"%s",s);
    memset(d,
0,sizeof(d));
    
for(i=0;i<maxl;++i){
        d[s[i]]
=i;
    }

    head
=tail=0;
    nnode
=0;
    q[
0].init();
    
while(m--){
        scanf(
"%s",s);
        insert(s);
    }

    build_ac_automation();
    nnode
++;
    solve();
    
return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理