hnu11187

AC自动机+DP

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

#define D(x)

const int MAX_D_LEN = ;

const int MAX_LEN = ;

const int MAX_N = ;

const int MAX_CHILD_NUM = ;

const int MAX_NODE_NUM = MAX_N * MAX_D_LEN;

const int INF = 0x3f3f3f3f;

char dna[MAX_LEN];

struct Trie

{

    int next[MAX_NODE_NUM][MAX_CHILD_NUM];

    int fail[MAX_NODE_NUM];

    bool disease[MAX_NODE_NUM];

    int node_cnt;

    bool vis[MAX_NODE_NUM]; //set it to false

    int root;

    int dp[MAX_LEN][MAX_NODE_NUM];

    void init()

    {

        node_cnt = ;

        root = newnode();

        memset(vis, , sizeof(vis));

    }

    int newnode()

    {

        for (int i = ; i < MAX_CHILD_NUM; i++)

            next[node_cnt][i] = -;

        disease[node_cnt++] = false;

        return node_cnt - ;

    }

    int get_id(char a)

    {

        return (int)a;

    }

    void insert(char buf[])

    {

        int now = root;

        for (int i = ; buf[i]; i++)

        {

            int id = get_id(buf[i]);

            if (next[now][id] == -)

                next[now][id] = newnode();

            now = next[now][id];

        }

        disease[now] = true;

    }

    void build()

    {

        queue<int>Q;

        fail[root] = root;

        for (int i = ; i < MAX_CHILD_NUM; i++)

            if (next[root][i] == -)

                next[root][i] = root;

            else

            {

                fail[next[root][i]] = root;

                Q.push(next[root][i]);

            }

        while (!Q.empty())

        {

            int now = Q.front();

            Q.pop();

            for (int i = ; i < MAX_CHILD_NUM; i++)

                if (next[now][i] == -)

                    next[now][i] = next[fail[now]][i];

                else

                {

                    fail[next[now][i]]=next[fail[now]][i];

                    if (disease[fail[next[now][i]]])

                        disease[next[now][i]] = true;

                    Q.push(next[now][i]);

                }

        }

    }

    int work(char* dna)

    {

        int len = strlen(dna);

        for (int i = ; i < node_cnt; i++)

        {

            if (disease[i])

                dp[len][i] = INF;

            else

                dp[len][i] = ;

        }

        for (int i = len - ; i >= ; i--)

        {

            int key = get_id(dna[i]);

            for (int j = ; j < node_cnt; j++)

            {

                if (disease[j])

                    continue;

                dp[i][j] = dp[i + ][root] + ;

                int v = next[j][key];

                if (disease[v])

                    continue;

                dp[i][j] = min(dp[i][j], dp[i + ][v]);

            }

        }

        return dp[][root];

    }

    void debug()

    {

        for(int i = ;i < node_cnt;i++)

        {

            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],disease[i]);

            for(int j = ;j < MAX_CHILD_NUM;j++)

                printf("%2d",next[i][j]);

            printf("]\n");

        }

    }

}ac;

int n, m;

char st[MAX_LEN];

int main()

{

    while (scanf("%d %d", &n, &m), n | m)

    {

        ac.init();

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

        {

            scanf("%s", st);

            getchar();

            ac.insert(st);

        }

        ac.build();

        int ans = ;

        for (int i = ; i < m; i++)

        {

            gets(st);

            ans += ac.work(st);

        }

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

    }

    return ;

}