算法1

AC自动机上DP

f[i][j][k]:长度为i，匹配到j状态，且（包含/不包含）单词的串的总数

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 110, M = 6010, MOD = 10007;
int tr[M][26], st[M], ne[M], idx;
int f[N][M][2];

int q[M], hh, tt;

int n, m;
char str[N];

void insert()
{
    int p = 0;
    for(int i = 0; str[i]; ++ i)
    {
        int t = str[i] - 'A';
        if(!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];
    }
    st[p] = true;
}

void build()
{
    hh = 0, tt = -1;
    for(int i = 0; i < 26; ++ i)
        if(tr[0][i])
            q[++ tt ] = tr[0][i];
    while(hh <= tt)
    {
        int t = q[hh ++ ];
        int tp = t;
        while(tp)
        {
            if(st[tp]) 
            {
                st[t] = true;
                break;
            }
            tp = ne[tp];
        }
        for(int i = 0; i < 26; ++ i)
        {
            int p = tr[t][i];
            if(!p) tr[t][i] = tr[ne[t]][i];
            else 
            {
                ne[p] = tr[ne[t]][i];
                q[++ tt ] = p;
            }
        }
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    while(n --)
    {
        scanf("%s", str);
        insert();
    }

    build();

    f[0][0][0] = 1;
    for(int i = 0; i < m; ++ i)
        for(int j = 0; j <= idx; ++ j)
            for(int k = 0; k < 2; ++ k)
                for(int u = 0; u < 26; ++ u)
                {
                    int v = tr[j][u];
                    (f[i + 1][v][k | st[v]] += f[i][j][k]) %= MOD;
                }

    int res = 0;
    for(int i = 0; i <= idx; ++ i)
        (res += f[m][i][1]) %= MOD;
    printf("%d", res);
    return 0;
}