CDOJ1633 Video Game Combos [AC自动机+dp]

　题目地址：http://acm.uestc.edu.cn/problem.php?pid=1633

　AC自动机+BFS

　AC自动机，参见：http://www.cnblogs.com/luna-lovegood/archive/2012/04/06/2434340.html

　先用给出的模式串构造AC automaton，再进行BFS即可。

代码：

//zzy2012.3.28AC
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>

using namespace std;

char chrn;
#define SCRN while(scanf("%c",&chrn) && chrn!='\n');

typedef struct
{
    int f,t,cnt;//f:最大前缀匹配的点；t：when enter the node,how many patterns are recognised；cnt 在dp时用
    int e[3];
}node;

typedef struct
{
    int idx,k,n;
}node2;

int N,K;
int top,front,rear,queue[10000];
node trie[3000];
node2 Q[10000000];

void push(int i)
{
    queue[rear++]=i;
}

int pop()
{
    front++;
    return queue[front-1];
}

void push2(node2 i)
{
    Q[rear++]=i;
}

node2 pop2()
{
    front++;
    return Q[front-1];
}

void ini()
{
    top=0;
    trie[0].f=-1;
    trie[0].t=0;
    trie[0].cnt=0;
    trie[0].e[0]=-1;
    trie[0].e[1]=-1;
    trie[0].e[2]=-1;
    top++;
}

void insert(int idx,char *s,int len)
{
    if(trie[idx].e[s[0]-'A']==-1)
    {
        trie[idx].e[s[0]-'A']=top;
        trie[top].f=0;
        trie[top].cnt=-1;
        trie[top].e[0]=-1;
        trie[top].e[1]=-1;
        trie[top].e[2]=-1;
        len--;
        if(len==0)
            trie[top++].t=1;
        else
        {
            trie[top].t=0;
            top++;
            insert(top-1,s+1,len);
        }
    }
    else
    {
        len--;
        if(len==0)
        {
            trie[trie[idx].e[s[0]-'A']].t++;
            return ;
        }
        else
            insert(trie[idx].e[s[0]-'A'],s+1,len);
    }
}

void struct_AC()//key function
{
    int i,r,v,u;
    for(i=0; i<3; i++)
        if(trie[0].e[i]==-1)
            trie[0].e[i]=0;
    front=rear=0;
    for(i=0; i<3; i++)
        if(trie[0].e[i]>0)
        {
            trie[trie[0].e[i]].f=0;
            push(trie[0].e[i]);
        }
    while(rear>front)//struct f and t for each node
    {
        r=pop();
        for(i=0; i<3; i++)
            if(trie[r].e[i]>-1)
            {
                u=trie[r].e[i];
                v=trie[r].f;
                while(trie[v].e[i]==-1){
                    v=trie[v].f;
                }
                trie[u].f=trie[v].e[i];
                trie[u].t+=trie[trie[v].e[i]].t;
                push(u);
            }
    }
}

int dp()
{
    int max=0,idx,i,j,sign,t;
    node2 r,u;
    r.idx=0;
    r.k=0;
    r.n=0;
    front=rear=0;
    push2(r);
    while(rear>front)
    {
        r=pop2();
        idx=r.idx;
        t=r.n;//trie[idx].cnt;
        if(t<trie[idx].cnt-1)
            continue;
        if(r.k==K-1)
        {
            for(i=0; i<3; i++)
            {
                if(trie[idx].e[i]>-1)
                {
                    j=trie[idx].e[i];
                    if(t+trie[j].t>max)
                        max=t+trie[j].t;
                }
                else
                {
                    j=trie[idx].f;
                    while(trie[j].e[i]==-1)
                        j=trie[j].f;
                    j=trie[j].e[i];
                    if(t+trie[j].t>max)
                        max=t+trie[j].t;
                }
                //cout<<"__max:"<<max<<' '<<idx<<' '<<j<<' '<<r.k<<endl;
            }
        }
        else
        {
            for(i=0; i<3; i++)
                if(trie[idx].e[i]>-1)
                {
                    j=trie[idx].e[i];
                    if(t+trie[j].t>trie[j].cnt)
                    {
                        trie[j].cnt=t+trie[j].t;
                        //cout<<"OP4---:"<<idx<<' '<<j<<' '<<r.k<<' '<<endl;
                        u.idx=j;
                        u.k=r.k+1;
                        u.n=trie[j].cnt;
                        //cout<<"  OP 1\n";
                        //printf("%c\n",'A'+i);
                        push2(u);
                    }
                }
                else
                {
                    j=trie[idx].f;
                    while(trie[j].e[i]==-1)
                        j=trie[j].f;
                    j=trie[j].e[i];

                    if(t+trie[j].t>trie[j].cnt)
                    {
                        trie[j].cnt=t+trie[j].t;
                        //cout<<"OP3: "<<idx<<" "<<j<<' '<<r.k<<' '<<endl;

                        u.idx=j;
                        u.k=r.k+1;
                        u.n=trie[j].cnt;
                        //cout<<"  OP2++++++++++++++++ \n";
                        //printf("%c\n",'A'+i);
                        push2(u);
                    }
                }
        }
    }
    return max;
}

int main()
{
    int i,num;
    char s[25];
    //freopen("1633in.txt","r",stdin);
    cin>>N>>K;
    SCRN
    ini();
    for(i=0; i<N; i++)
    {
        gets(s);
        insert(0,s,strlen(s));
    }
    struct_AC();
    num=dp();
    cout<<num<<endl;
    return 0;
}