本文共 2148 字，大约阅读时间需要 7 分钟。

题目描述：给出n个字符串，求只出现在k个字符串中的子串最长有多长。

输入描述：第一行两个整数n,k，接着下来n行，每行一个字符串，全部由小写字母组成。

输出描述：一个数，表示最长的子串长度。

样例输入： 3 2 abckdeabcdeabc

样例输出： 2

样例解释：答案为de。abc虽然很长，但出现在了三个字符串中，所以不能作为答案。

数据范围：2 ≤ n ≤ 1000，每个字符串的长度 ≤ 1000，数据随机出。

题解： 其实并不是什么难题。

最初，我打算使用后缀数组来解决这个问题，后来发现不太适合，改为使用后缀自动机。后缀自动机是一种高效处理字符串的问题的数据结构，非常适合这个问题。

具体来说，我们需要找到一个最长的子串，这个子串只出现在k个字符串中。后缀自动机可以帮助我们高效地找到这个子串。

构建后缀自动机时，我们需要记录每个状态的出现次数。然后，通过统计每个状态的出现次数，我们可以确定哪些子串出现的频率满足条件。

最后，我们遍历所有可能的子串，找出满足出现次数等于k的最长子串。

代码实现：

#include 
   
    
#include 
    
     
const int N = 560 * 1005;
struct node {
    int son[26], pre, step;
} s[N];
int last, tot;
int n, m;
int vis[N], cnt;
void ins(int x) {
    int np = ++tot;
    s[np].step = s[last].step + 1;
    while (last != 0 && s[last].son[x] == 0) {
        s[last].son[x] = np;
        last = s[last].pre;
    }
    if (last == 0) {
        s[np].pre = 1;
    } else {
        int q = s[last].son[x];
        if (s[q].step == s[last].step + 1) {
            s[np].pre = q;
        } else {
            int nq = ++tot;
            s[nq] = s[q];
            s[nq].step = s[last].step + 1;
            s[q].pre = nq;
            while (last != 0 && s[last].son[x] == q) {
                s[last].son[x] = nq;
                last = s[last].pre;
            }
        }
    }
    last = np;
}
int main() {
    memset(vis, 0, sizeof(vis));
    cnt = 0;
    tot = 1;
    scanf("%d %d", &n, &m);
    for (int u = 1; u <= n; u++) {
        cnt++;
        int Last = tot + 1;
        last = 1;
        char ch = getchar();
        while (ch < 'a' || ch > 'z') ch = getchar();
        while (ch >= 'a' && ch <= 'z') {
            ins(ch - 'a');
            ch = getchar();
        }
        for (int i = Last; i <= tot; i++) {
            int x = i;
            while (x != 0 && vis[x] != cnt) {
                vis[x] = cnt;
                s[x].lalal++;
                x = s[x].pre;
            }
        }
    }
    int ans = 0;
    for (int u = 1; u <= tot; u++) {
        if (s[u].lalal == m) {
            ans = ans > s[u].step ? ans : s[u].step;
        }
    }
    printf("%d\n", ans);
    return 0;
}
    
   

这段代码首先构建后缀自动机，然后统计每个状态的出现次数，最后找到满足条件的最长子串。这种方法在数据范围内是高效且可行的。