程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3247

HDU 3247

編輯:C++入門知識

AC自動機

先預處理所有可以作為合法單詞結尾的點之間的距離,然後在這些點之間狀態DP即可

[cpp]
#include <stdio.h> 
#include <string.h> 
#define INF 0x3f3f3f3f 
#define MAXN 60005 
char s[1002]; 
int n,m; 
int next[MAXN][2],fail[MAXN],flag[MAXN],pos; 
int newnode(){ 
    next[pos][0]=next[pos][1]=0; 
    fail[pos]=flag[pos]=0; 
    return pos++; 

void insert(char *s,int id){ 
    int p=0; 
    for(int i=0;s[i];i++){ 
        int k=s[i]-'0',&x=next[p][k]; 
        p=x?x:x=newnode(); 
    } 
    if(id==-1)flag[p]=-1; 
    else flag[p]|=(1<<id); 

int q[MAXN],front,rear; 
void makenext(){ 
    q[front=rear=0]=0,rear++; 
    while(front<rear){ 
        int u=q[front++]; 
        for(int i=0;i<2;i++){ 
            int v=next[u][i]; 
            if(v==0)next[u][i]=next[fail[u]][i]; 
            else q[rear++]=v; 
            if(v&&u){ 
                fail[v]=next[fail[u]][i]; 
                if(flag[fail[v]]==-1)flag[v]=-1; 
                else flag[v]|=flag[fail[v]]; 
            } 
        } 
    } 

#define MAXM 1025 
int d[MAXN][MAXM],pnt[MAXM],ps,map[MAXM][MAXM],dis[MAXN]; 
inline int min(int x,int y){return x<y?x:y;} 
void bfs(int p){ 
    for(int i=0;i<pos;i++)dis[i]=INF; 
    q[front=rear=0]=pnt[p],rear++; 
    dis[pnt[p]]=0; 
    while(front<rear){ 
        int u=q[front++]; 
        for(int i=0;i<2;i++){ 
            int v=next[u][i]; 
            if(flag[v]<0||dis[v]!=INF)continue; 
            dis[v]=dis[u]+1; 
            q[rear++]=v; 
        } 
    } 
    for(int i=0;i<ps;i++)map[p][i]=dis[pnt[i]]; 

int dp(){ 
    for(int i=0;i<(1<<n);i++)for(int u=0;u<ps;u++)d[i][u]=INF; 
    d[0][0]=0; 
    for(int i=0;i<(1<<n);i++){ 
        for(int u=0;u<ps;u++){ 
            if(d[i][u]==INF)continue; 
            for(int v=0;v<ps;v++) 
                d[i|flag[pnt[v]]][v]=min(d[i|flag[pnt[v]]][v],d[i][u]+map[u][v]); 
        } 
    } 
    int ans=INF; 
    for(int i=0;i<ps;i++) 
        ans=min(ans,d[(1<<n)-1][i]); 
    return ans; 

int main(){ 
    while(scanf("%d%d",&n,&m),n||m){ 
        pos=0;newnode(); 
        for(int i=0;i<n;i++){ 
            scanf("%s",s); 
            insert(s,i); 
        } 
        for(int i=0;i<m;i++){ 
            scanf("%s",s); 
            insert(s,-1); 
        } 
        makenext(); 
        ps=0; 
        for(int i=0;i<pos;i++) 
            if(i==0||flag[i]>0)pnt[ps++]=i; 
        for(int i=0;i<ps;i++) 
            bfs(i); 
        printf("%d\n",dp()); 
    } 
    return 0; 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved