POJ1699【AC自动机+状压DP

萌新感言：

我的天呐！

因为是AC自动机的专题所以没有管别的。。。硬着头皮吃那份题解（代码）。。【请戳简单美丽可爱的代码（没开玩笑）】

首先讲AC自动机：

tag存的是以这个节点为后缀的字符串个数（已状压）。

我们在构造fail指针的时候，采用的是BFS的手段，对于树而言，那就是一层一层的向下遍历，

所以代码很巧妙（不能说巧妙吧，就是这样的），在找到fail位置的时候直接跳出，然后更新了tag，为什么可以这样?因为长的找到的时候，短的早就找过了，所以直接更新就好了。

然后这份代码有一个小瑕疵（讲错请吐槽！）：因为在构造fail指针的时候tag已经更新过了，所以在DP的时候没必要再找到fail指针然后更新。

自身问题（可跳过）：

还有构造fail的函数中当节点不存在的时候，这个节点的位置，用父节点的这个元素的fail指针取代了，如图：

道理还是一样，我要保证长的找到的时候，短的早就找过了。

然后讲DP：

感觉AC自动机下的DP很好理解，因为Trie树上本身对于每个节点就是一种种状态，用BFS的手段从上层到下层遍历。

DP[ i ][ j ]表示匹配到 i 节点，匹配到 j 个字符串时的最短步数。

每次只会伸展一个新节点，从而获取更多的后缀串，所以

dp[x][new_string_num]=min(dp[x][new_string_num],dp[x的父节点][old_string_num]+1);

that's all,thanks for watching....

//#include <bits/stdc++.h>

#include<iostream>

#include<queue>

#include<cstdio>

#include<string.h>

#include<algorithm>

using namespace std;

typedef pair<int,int> PII;

const int N=205;

const int INF=0x3f3f3f3f;

int n,dp[N][1030];

int g[N][4],fail[N],tag[N];

int sz;

void init()

{

    sz=1;

    tag[0]=0;

    memset(g[0],0,sizeof(g[0]));

}

int GetID(char x)

{

    if(x=='A') return 0;

    if(x=='T') return 1;

    if(x=='C') return 2;

    return 3;

}

void INS(char *str,int id)

{

    int len=strlen(str),index,root=0;

    for(int i=0;i<len;i++){

        index=GetID(str[i]);

        if(g[root][index]==0)

        {

            tag[sz]=0;

            memset(g[sz],0,sizeof(g[sz]));

            g[root][index]=sz++;

        }

        root=g[root][index];

    }

    tag[root]|=(1<<id);

}

void Build_fail()

{

    queue<int>que;

    for(int i=0;i<4;i++)

    {

        int u=g[0][i];

        if(u){

            fail[u]=0;

            que.push(u);

        }

    }

    while(!que.empty())

    {

        int root=que.front();

        que.pop();

        for(int i=0;i<4;i++){

            int u=g[root][i];

            if(!u){

                g[root][i]=g[fail[root]][i];//如果这个节点不存在 用父节点的这个元素的fail指针取代了

                continue;

            }

            que.push(u);

            int v=fail[root];

            while(v && g[v][i]==0)

                v=fail[v];

            fail[u]=g[v][i];    //构造

            tag[u]|=tag[fail[u]]; //更新节点存的字符串个数。

        }

    }

}

int solve()

{

    //初始化

    Build_fail();

    memset(dp,INF,sizeof(dp));

    dp[0][0]=0;

    queue<PII>que;

    que.push(make_pair(0,0));//塞入根节点，匹配0；

    while(!que.empty())

    {

        int u=que.front().first;

        int s=que.front().second;

        que.pop();

        for(int i=0;i<4;i++){

            int k=g[u][i];      //匹配这个节点，因为之前当节点不存在的时候已经存了父节点的该元素的fail指针，所以不用考虑为空

            int ss=s|tag[k];    //在建立fail指针的时候，tag[k]存的字符串个数已经更新

            if(dp[k][ss]>dp[u][s]+1)

            {

                dp[k][ss]=dp[u][s]+1;

                que.push(make_pair(k,ss));

                if(ss==(1<<n)-1)

                    return dp[k][ss];

            }

        }

    }

    return 0;

}

int main()

{

    int T;

    char s[30];

    scanf("%d",&T);

    while(T--){

        init();

        scanf("%d",&n);

        for(int i=0;i<n;i++)

        {

            scanf("%s",s);

            INS(s,i);

        }

        printf("%d\n",solve());

    }

    return 0;

}

巴特西

POJ1699【AC自动机+状压DP_感言】

最新文章

热门文章