原题链接，不是权限题

题目大意

有\(n\)个模板串，让你构造一个尽量长的串，使得这个串中任意一个长度为\(k\)的子串都是至少一个模板串的子串

题解

可以先看一下这道题 [POI2000]病毒

虽然是个\(AC\)自动机，不过思路很像

对于这道题，我们只需要把广义\(SAM\)建出来，然后在那些只经过\(maxlen\geqslant k\)的结点的路径中选一个最长的就行了。最后一步可以用拓扑排序来完成

拓扑建边时可以直接向\(fail\)连边，而不是把儿子补全（像\(AC\)自动机那样\(ch[u][c]=ch[fail[u]][c]\)），这样能降低复杂度

最后如果出现环，就输出\(INF\)，否则求最长路径，注意特判所有结点的\(maxlen\)都小于\(k\)的情况，题目最下方有说明

丑的一批的代码奉上：

#include <algorithm>

#include  <iostream>

#include   <cstdlib>

#include   <cstring>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <cmath>

#include     <ctime>

#include     <queue>

#include       <map>

#include       <set>

using namespace std;

#define ull unsigned long long

#define pii pair<int, int>

#define mii map<int, int>

#define uint unsigned int

#define lbd lower_bound

#define ubd upper_bound

#define ll long long

#define mp make_pair

#define pb push_back

#define re register

#define il inline

#define N 100000

int n, k;

char s[N+5];

int root, nid, last, ch[2*N+5][26], fail[2*N+5], len[2*N+5];

int in[2*N+5], d[2*N+5];

vector<pii> G[2*N+5];

void clear() {

  root = nid = 1;

  memset(ch[1], 0, sizeof ch[1]);

  memset(fail, 0, sizeof fail);

  memset(in, 0, sizeof in);

  memset(d, 0, sizeof d);

  // memset(len, 0, sizeof len);

  G[1].clear(), G[2*N+2].clear(), G[2*N+3].clear();

}

void init() {

  last = root;

}

void extend(int c) {

  int cur = ++nid;

  memset(ch[cur], 0, sizeof ch[cur]);

  G[cur].clear();

  len[cur] = len[last]+1;

  while(last && !ch[last][c]) ch[last][c] = cur, last = fail[last];

  if(!last) fail[cur] = root;

  else {

    int p = last, q = ch[last][c];

    if(len[q] == len[p]+1) fail[cur] = q;

    else {

      int clone = ++nid;

      G[clone].clear();

      len[clone] = len[p]+1;

      for(int i = 0; i < 26; ++i) ch[clone][i] = ch[q][i];

      fail[clone] = fail[q], fail[q] = fail[cur] = clone;

      while(p && ch[p][c] == q) ch[p][c] = clone, p = fail[p];

    }

  }

  last = cur;

}

int topo() {

  int S = 2*N+2, T = 2*N+3, ans = 0, cnt = 0;

  d[T] = 0;

  G[S].clear();

  for(int i = 1; i <= nid; ++i)

    if(len[i] == k-1) {

      for(int j = 0; j < 26; ++j) if(ch[i][j]) G[i].pb(mp(ch[i][j], 1)), in[ch[i][j]]++;

      in[i]++;

      G[S].pb(mp(i, len[i]));

    }

    else if(len[i] >= k) {

      for(int j = 0; j < 26; ++j) if(ch[i][j]) G[i].pb(mp(ch[i][j], 1)), in[ch[i][j]]++;

      if(fail[i] && len[fail[i]] >= k-1) G[i].pb(mp(fail[i], 0)), in[fail[i]]++;

      G[i].pb(mp(T, 0));

      G[S].pb(mp(i, len[i]));

      in[T]++, in[i]++;

      cnt++;

    }

  if(!cnt) return k-1;

  queue<int> q;

  q.push(S);

  while(!q.empty()) {

    int u = q.front(); q.pop();

    ans = max(ans, d[u]);

    for(int i = 0; i < G[u].size(); ++i) {

      int v = G[u][i].first, w = G[u][i].second;

      in[v]--;

      d[v] = max(d[v], d[u]+w);

      if(!in[v]) q.push(v);

    }

  }

  for(int i = 1; i <= nid; ++i) if(in[i]) return -1;

  return ans;

}

int main() {

  while(~scanf("%d%d", &n, &k)) {

    clear();

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

      scanf("%s", s);

      int len = strlen(s);

      init();

      for(int j = 0; j < len; ++j) extend(s[j]-'a');

    }

    int ans = topo();

    if(ans == -1) printf("INF\n");

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

  }

  return 0;

}