CloudySky

纵使世界万般残酷

总有温暖值得守护

CF235C Cyclical Quest

题目描述

给定一个文本串，和 nn 个模式串。求每个模式串和它的循环同构串在文本串中出现的总次数。

题目正解

后缀自动机 SAMSAM

题目思路

就这个题思考一下把 SAMSAM 当成文本匹配工具的做法。

首先回忆一条性质 “从初始节点 t0t_0 开始的任意一条路径都与 ss 的子串构成对应关系”。

这就注定 SAMSAM 可以作为一种字符串匹配工具。且在空间复杂度以外比 ACAC 自动机更加优秀。

设匹配长度为 kk，对于文本串 TT 只需要暴力跳 samsam 转移边同时将 k++k++。失配之后直接跳 failfail 同时 k=len[p]k = len[p] 然后继续匹配即可。因为当前点的匹配值一定是大于 maxlenfailpmaxlen_{fail_p} 的，否则它不会跳到当前节点，所以失配后长度一定是 failpfail_p 等价类中最长的。

对于这道题来讲。先把整个串完整匹配出来。然后开始在前面逐个删字符的同时在后面加字符继续匹配，当匹配长度达到串长直接将当前节点的 sizsiz 统计到答案里。

对于在前面删字符，不需要进行任何实质上的删除，只需要将匹配长度 −1-1，直到匹配长度不在 [minlenp,maxlenp][minlen_p, maxlen_p] 这个区间跳 failfail 即可。

但是你发现直接这样做是不对的。如果这个字符串的两个循环子串完全相等的话答案将被重复统计，如 abababab 当起始位置为 11 和 33 时这个字符串时完全一样的，所以在用过的节点上需要打上标记。然后char vis[Maxn];活活气死自己

题目代码

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO // namespace IO
using namespace IO;
const int Maxn = 2e6 + 10;
using namespace std;
 
char s[Maxn];
int sam[Maxn][26], siz[Maxn], len[Maxn], fail[Maxn], lst, tot;
 
void insert(char c) {
  int p = lst, np = ++tot, ch = c - 'a';
  lst = np, len[np] = len[p] + 1, siz[np] = 1;
  for (; p != -1 && !sam[p][ch]; p = fail[p]) sam[p][ch] = np;
  if (p == -1) return fail[np] = 0, void();
  int q = sam[p][ch];
  if (len[q] == len[p] + 1) return fail[np] = q, void();
  int nq = ++tot;
  fail[nq] = fail[q], fail[q] = fail[np] = nq;
  memcpy(sam[nq], sam[q], sizeof(sam[nq]));
  len[nq] = len[p] + 1;
  for (; p != -1 && sam[p][ch] == q; p = fail[p]) sam[p][ch] = nq;
}
 
void SAM() {
  fail[0] = -1, lst = tot = 0;
  int n = strlen(s);
  for (int i = 0; i < n; ++i) insert(s[i]);
  static int cnt[Maxn], id[Maxn];
  for (int i = 0; i <= tot; ++i) ++cnt[len[i]];
  for (int i = 0; i <= tot; ++i) cnt[i] += cnt[i - 1];
  for (int i = 0; i <= tot; ++i) id[--cnt[len[i]]] = i;
  for (int i = tot; i; --i) siz[fail[id[i]]] += siz[id[i]];
  print(tot + 1);
}

char t[Maxn]; int vis[Maxn];
 
void solve(int tim) {
  scanf("%s", t + 1);
  int n = strlen(t + 1), k = 0, p = 0; long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    int ch = t[i] - 'a';
    while (p != 0 && !sam[p][ch]) k = len[p = fail[p]];
    if (sam[p][ch]) p = sam[p][ch], ++k;
  }
  for (int i = 1; i <= n; ++i) {
    int ch = t[i] - 'a';
    if (k == n) {
      if (vis[p] != tim) ans += siz[p], vis[p] = tim;
      if (--k == len[fail[p]]) p = fail[p];
    }
    while (p != 0 && !sam[p][ch]) k = len[p = fail[p]];
    if (sam[p][ch]) p = sam[p][ch], ++k;
  }
  print(ans);
}
 
signed main() {
  scanf("%s", s), SAM();
  int m = read();
  for (int i = 1; i <= m; ++i) solve(i);
  return 0;
}

本文作者：CloudySky
写作时间： 2022-03-12
最后更新时间： 2022-03-12
遵循协议： BY-NC-SA

Top