BZOJ5261 Rhyme——广义SAM+拓扑排序

原题链接，不是权限题

题目大意

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

题解

可以先看一下这道题 [POI2000]病毒
虽然是个\(AC\)自动机，不过思路很像
对于这道题，我们只需要把广义\(SAM\)建出来，然后在那些只经过\(maxlen\geqslant k\)的结点的路径中选一个最长的就行了。最后一步可以用拓扑排序来完成
拓扑建边时可以直接向\(fail\)连边，而不是把儿子补全（像\(AC\)自动机那样\(ch[u][c]=ch[fail[u]][c]\)），这样能降低复杂度
最后如果出现环，就输出\(INF\)，否则求最长路径，注意特判所有结点的\(maxlen\)都小于\(k\)的情况，题目最下方有说明
丑的一批的代码奉上：

#include 
#include  
#include   
#include   
#include    
#include    
#include    
#include     
#include     
#include     
#include       
#include       
 
using namespace std;
 
#define ull unsigned long long
#define pii pair
#define mii map
#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 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 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;
}
字符串——后缀自动机SAM字符串后缀自动机SAM

相关

js 正则匹配 两个字符串之间，某个字符串之前（之后）的内容

大爽Python入门教程 1-2 数与字符串

Java21-统计字符串中每个字符出现的次数

全（十五）Jmeter 之 参数化 函数助手：__Random string（译：瑞德.丝锥）：随机字符串

生成随机字符串

09练习：统计输入的字符串中各种字符的个数

2-14str1转义字符，格式化_2-15str2格式化，字符串内置函数

python基本数据类型；关于字符串格式化的补充

Java基础-02 字符串(汉字)与16进制字符串转换(无乱码)

C语言判断给定的字符串是否为合法的ip地址的代码-C-J

把字符串a复制到字符串b，利用指针

javascript模板字符串（反引号）

标签