Rockdu's Blog

4 5
monika
tomek
szymon
bernard

23​
 ​

这题好想，就是处理每一个字符串AC自动机结尾到另一个结尾的最短路矩阵加速。

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5;
const int N = 2e2 + 5;
int n, m;
char s[maxn];

struct edge {
    int v, next, w;
}e[maxn << 2];
int head[maxn], cnt, key[maxn], bg[maxn];
void adde(const int &u, const int &v, const int &w) {
    e[++cnt] = (edge) {v, head[u], w};
    head[u] = cnt;
}
int len;
LL mat[N][N], pow[N][N], tmp[N][N];
namespace AC {
    int trie[maxn][26], cnt = 1, fa[maxn];
    int insert(char * s) {
        len = strlen(s);
        int now = 1, id;
        for(register int i = 0; i < len; ++i) {
            id = s[i] - 'a';
            if(trie[now][id]) now = trie[now][id];
            else now = trie[now][id] = ++cnt;
        }
        return now;
    }
    void create() {
        int v, u, p;
        queue<int > q;q.push(1);
        while(!q.empty()) {
            u = q.front();
            q.pop();
            for(register int i = 0; i < 26; ++i) {
                if(!trie[u][i]) continue;
                v = trie[u][i], p = fa[u];
                adde(u, v, 1);
                while(p && !trie[p][i]) p = fa[p];
                if(!p) fa[v] = 1;
                else fa[v] = trie[p][i];
                adde(v, fa[v], 0);
                q.push(v);
            }
        }
    }
}

int vis[maxn];LL dis[maxn];
void spfa(int st) {
    int in = 0;
    queue<int > q;
    memset(dis, 0x3f, sizeof(dis));
    q.push(key[st]), dis[key[st]] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop(), vis[u] = 0;
        for(register int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if(dis[u] + e[i].w < dis[v]) {
                dis[v] = dis[u] + e[i].w;
                if(!vis[v]) vis[v] = 1, q.push(v);
            }
        }
        if(!in) dis[u] = 0x3f3f3f3f3f3f3f3f, in = 1;
    }
    for(register int i = 1; i <= n; ++i)
        mat[st][i] = dis[key[i]];
}

void mul(LL a[N][N], LL b[N][N]) {
    memset(tmp, 0x3f, sizeof(tmp));
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= n; ++j)
            for(register int k = 1; k <= n; ++k)
                tmp[j][k] = min(a[j][i] + b[i][k], tmp[j][k]);
    memcpy(a, tmp, sizeof(tmp));
}

void fpow(LL a[N][N], int b) {
    while(b) {
        if(b & 1) mul(pow, a);
        b >>= 1, mul(a, a);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= n; ++i)
        scanf("%s", s), key[i] = AC::insert(s), bg[i] = len;
    AC::create();
    for(register int i = 1; i <= n; ++i) spfa(i);
    if(m > 1) {
        memcpy(pow, mat, sizeof(mat));
        fpow(mat, m - 2);
    }
    LL ans = 0x3f3f3f3f3f3f3f3f;
    for(register int i = 1; i <= n; ++i) 
        for(register int j = 1; j <= n; ++j)
            ans = min(ans, pow[i][j] + bg[i]);
    printf("%lld", ans);
    return 0;
}