[CF235C]后缀自动机

题目大意:给定一个主串 $S$ 和 $m$ 个询问串,求每个询问串的循环同构在主串中的出现次数之和

可以考虑如何处理循环同构这一限制条件,一种套路的做法就是将每一个询问串复制一遍,这样每一次依旧匹配,如果匹配超过其原长度就可以对答案造成贡献

对于每一个点的贡献可以用类似 $dp$ 的做法得到,可以求出每个节点以其为前缀的所有串的个数

但是循环同构中遇到 $aa$ 这样的串会算两次 $aa$ 的贡献,需要考虑如何去重,一种做法是记录每一个点是否统计过答案,如果统计过就不再统计

具体的统计贡献做法是:设当前点为 $u$ ,所有以其为 $fail$ 的点都是可以对该点造成贡献,所以
$$
f_u=\sum_{v \in son}f_v
$$
注意所有一开始在后缀自动机上的点(不包括 $clone$ )的 $f_u=1$ 即空串也会造成贡献

另外后缀自动机上的匹配如下

  • 首先设 $p=1,len=0$ 表示当前在根节点,匹配长度为 $len$
  • 查询当前 $p$ 节点是否有 $s_i$ 儿子,如果没有则一直跳 $fail$ 直到找到,每一次跳 $fail$ 需要将 $len$ 更新为 $Tree[p].len$
  • 如果当前匹配长度 $len\ge n$ 表示匹配足够的点,那么就可以统计贡献并且打上标记
  • 特别的,如果 $Tree[Tree[p].fail].len \ge n$ 表示当前点 $fail$ 同样可以造成贡献,那么可以让 $p$ 跳到它的 $fail$ 来统计答案,因为如果不跳会造成漏记答案
  • 同时,如果改点被打过标记,那么该点贡献忽略
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/***************************************************************
File name: CF235C.cpp
Author: ljfcnyali
Create time: 2019年11月25日 星期一 21时42分15秒
***************************************************************/
#include<bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i )
#define mem(a) memset ( (a), 0, sizeof ( a ) )
#define str(a) strlen ( a )
#define pii pair<int, int>
typedef long long LL;

const int maxn = 2e6 + 10;

struct node { int Next[26], len, fa; } Tree[maxn];
int n, m, N, last = 1, tot = 1, f[maxn], Begin[maxn], Next[maxn], To[maxn], e;
bool vis[maxn];
char s[maxn];
vector<int> Rub;

inline void add(int u, int v) { To[++ e] = v; Next[e] = Begin[u]; Begin[u] = e; }

inline void Extand(int c)
{
int cur = ++ tot; f[cur] = 1;
Tree[cur].len = Tree[last].len + 1;
int p = last; last = cur;
while ( p && !Tree[p].Next[c] ) { Tree[p].Next[c] = cur; p = Tree[p].fa; }
if ( !p ) { Tree[cur].fa = 1; return ; }
int q = Tree[p].Next[c];
if ( Tree[p].len + 1 == Tree[q].len ) Tree[cur].fa = q;
else
{
int clone = ++ tot;
Tree[clone] = Tree[q]; Tree[clone].len = Tree[p].len + 1;
while ( p && Tree[p].Next[c] == q ) { Tree[p].Next[c] = clone; p = Tree[p].fa; }
Tree[cur].fa = Tree[q].fa = clone;
}
}

inline void DFS(int u)
{
for ( int i = Begin[u]; i; i = Next[i] )
{
int v = To[i]; DFS(v);
f[u] += f[v];
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%s", s + 1); n = str(s + 1);
REP(i, 1, n) Extand(s[i] - 'a');
REP(i, 2, tot) add(Tree[i].fa, i);
DFS(1);
scanf("%d", &m);
while ( m -- )
{
scanf("%s", s + 1); N = str(s + 1);
REP(i, 1, N) s[i + N] = s[i]; N += N;
int ans = 0, p = 1, len = 0;
REP(i, 1, N - 1)
{
int c = s[i] - 'a';
while ( p != 1 && !Tree[p].Next[c] ) { p = Tree[p].fa; len = Tree[p].len; }
if ( Tree[p].Next[c] ) { p = Tree[p].Next[c]; ++ len; }
while ( p != 1 && Tree[Tree[p].fa].len >= N / 2 ) { p = Tree[p].fa; len = Tree[p].len; }
if ( len >= N / 2 && !vis[p] ) { ans += f[p]; vis[p] = true; Rub.push_back(p); }
// if ( len >= N / 2 ) printf("%c %d %d\n", s[i], f[p], len);
}
for ( auto i : Rub ) vis[i] = false; Rub.clear();
printf("%d\n", ans);
}
return 0;
}