前言
应该是算竞生涯的最后两、三个月了，现在打算直接all in字符串，看看到时候能不能碰上个开的出来的字符串题，下面是一些做题的题的记录和经验总结。
性质总结
昨天VP了23年CCPC哈尔滨，中场时候看到C是串串，兴奋地开了一整场，最后连方向都错了。感觉就是因为之前学的时候太快了，就刚学完各个科技时候记得清楚，现在隔一段时间后，border树, fail树， parent树的性质都记混了。所以这里打算回顾一下之前学的时候做的题，分类总结一下性质。
border 树
是KMP，把每个 \(i\) 向 \(nxt[i]\) 连边后得到的树，每个节点代表一个前缀, 树上的父亲是对应前缀的border。子树大小意味着这个border在原串中的出现次数，可以利用树状数组离线，来动态维护这个border树的真实子树大小。题目链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71338847
AC自动机fail树
AC自动机是离线的数据结构解决多模式串匹配问题，模板应用是给定文本串\(S\)，和多个模式串 \(T\) , 分别求各个 \(T\) 在 \(S\) 里出现了多少次。
常是对多的模式串建立AC自动机后，将文本串S在上面跑，每跑到一个节点，该节点表示的串是跟模式串前缀的最长公共后缀，并且跑到一个节点，表明到根节点的所有fail树上节点都能匹配到。比较重要的一点是fail树节点编号不会自然拓扑序，所以不能直接从大到小往 \(fail[i]\) 上递推，得拓扑排序，或者建图后dfs。一个串的出现次数，等于fail树子树内所有标记节点的个数，标记节点是一个串的最后一个字母在ac自动机上的节点。所以可以用树状数组+dfn序来维护出现次数。
不包含字典串的限制也可以用字符串匹配来做，在ac自动机上顺着转移边转移，如果会走到终止节点则非法。
无限长度且不在字典串的字符串，等价于在ac自动机上不包含终止节点的一个环，用拓扑找环，并且能从根节点出发走到。
而且也经常可能要把题目的字符串翻转等，来符合ac自动机的性质条件。
问一个串的所有子串，可以把这个串在ACAM上跑，每跑到一个节点，该节点到根的链上所有节点都是它的子串，就可以结合树剖来维护这些信息。而SAM没办法快速维护这样所有子串，在parent树上没有明显关系，恰有两个串的时候可能可以利用endpos来维护出子串关系。
PAM
模板应用是给定一个字符串，可以求出所有本质不同回文子串的数量、长度、出现次数。
PAM回文树有2棵，分别表示奇回文和偶回文，trie图上只能在同一棵树内转移，fail指针可能会跨树，fail指针含义是指向当前回文串的最长回文后缀，可以在建树过程中轻松地维护出字符串里以每个位置为回文右端点的回文子串数量。并且编号从大到小就是拓扑序。回文串的出现次数也是等价于fail树子树求和。
求总的回文串个数有两种求法跟理解，一个是求出以每个位置作为右端点的回文串数量，在建树过程中等价于fail树的深度求和，建一遍顺便就求好了。另一个是对每个本质不同的回文子串数量求和，是建的过程里cnt[lst]++，最后拓扑序fail树累加后，在对每个结点的cnt累加。
PAM的最高级应用就是利用border的等差数列性质优化dp。大概就是等差数列会在偏移公差后再次出现，dp值只会相差一个位置。所以可以在建图的时候，顺便维护每个等差数列的dp值。典题包括，求一个字符串的(偶)回文串划分方案、最小花费回文串划分。
SAM
是能接受一个字符串所有子串的自动机，模板应用是求一个字符串所有本质不同子串个数、长度、检查一个模式串是否在文本串里出现(沿着转移图走，走不了即没出现)。
SAM在字符集大的时候，可以直接把c[maxn][26]换成map，clone时候对应改改即可。一个比较关键的性质是SAM编号没有拓扑序，要么直接建出来fail树再dfs，要么先按照节点长度基数排序后再从大到小枚举。每一个前缀在SAM上对应的节点代表了一个endpos，SAM上一个字符串出现的次数等价于fail树子树内所有endpos的个数，也常跟dfs序结合维护子树，所以也可以维护endpos的最大、最小值，倍增跳到endpos满足某个性质的节点。字符串出现次数常转化为满足某个条件的endpos个数。
SAM应用
求一个串的循环串的最小字典序:复制一遍建SAM，每次在转移图上走最小边。
求一个串的子串[l,r]在原串的[L, R]的出现次数：等价于倍增找到[l, r]对应节点，子树内endpos满足[L,R]的个数，可主席树，可离线差分。
求多个串的最长公共子串:用最短的串建SAM，其他串在上面跑，求出每个结点能匹配上第 \(i\) 个串的最长字串长度，这里需要拓扑更新取max，能匹配到一个节点，一定也能匹配到fail树到根路径上的所有节点(还得跟节点的len取min)，最后枚举节点，能表示各个串的最长长度取min。
CF963D
题目大概是给一个字符串S，又有很多询问，给k 和 T，要找S最小的区间，使得区间内包含k个T。
在评论区学到了一种用bitset来维护字符串的endpose集合的方法，在数据范围不是特别大的时候可以用,而且可以使用bitset的_Find_first() 以及 _Find_next(x)函数，可以用来遍历bitset的所有1的位置。
复杂度 \(O(\frac{|S|\times \sum |T|}{w})\)
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
bitset
void solve() {
string str; cin >> str;
int n = str.length();
for (int i = 1; i <= n; i++)
bs[str[i - 1] - 'a'][i] = 1;
int q; cin >> q;
while (q--) {
cur.set();
int k; cin >> k;
string s; cin >> s;
int m = s.length();
for (int j = 1; j <= m; j++) {
cur &= (bs[s[j - 1] - 'a'] << (m - j));
}
if (cur.count() < k) {
cout << -1 << "\n";
continue;
}
vector
for (auto it = cur._Find_first(); it != maxn; it = cur._Find_next(it))
vec.push_back(it);
int ans = inf;
for (int i = k - 1; i < vec.size(); i++)
ans = min(ans, vec[i] - vec[i - k + 1] + m);
cout << ans << "\n";
}
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
CF914F
和刚刚那题差不多，要求带修的字符串，查询区间内，某个字符串出现次数，也是可以用bitset维护一下就好。不过区别在于这题不能暴力遍历1的位置，得直接用移位加count()来统计。
刚刚看了下证明，因为上一题有保证所有查询字符串互不相同，所以endpos大小和是 \(n \sqrt(n)\) ，这题没有保证这个，所以暴力遍历1会超时。
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
bitset
void solve() {
string str; cin >> str;
int n = str.length();
for (int i = 1; i <= n; i++)
bs[str[i - 1] - 'a'][i] = 1;
int q; cin >> q;
while (q--) {
int op; cin >> op;
if (op == 1) {
int pos; char ch;
cin >> pos >> ch;
bs[str[pos - 1] - 'a'][pos] = 0;
str[pos - 1] = ch;
bs[str[pos - 1] - 'a'][pos] = 1;
} else {
int l, r; string s;
cin >> l >> r >> s;
cur.set();
int m = s.length();
for (int j = 1; j <= m; j++)
cur &= bs[s[j - 1] - 'a'] << (m - j);
int ans = (cur >> (l + m - 1)).count() - (cur >> (r + 1)).count();
cout << max(0, ans) << "\n";
}
}
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
cf666E
给定文本串S，又给出 \(m\) 个串，多次询问，每次询问S串的一个子串[l,r]在第 \(L\) 到第 \(R\) 个T串里的哪一个出现位置最多
因为是在T里面出现，所以是需要对T串建SAM，又因为有多个串，所以要建广义SAM。对于子串的限制，可以套路的预处理 \(to[i]\) 表示S串的每个前缀能匹配上SAM节点的最长后缀位置，然后倍增跳到对应节点。问题转化为endpos是查询区间内的T串子树内数颜色问题，所以用权值线段树加线段树合并，这里注意写法，合并时候开很多新点，不要复用，空间记得开大，而且合并函数里面得存一下now，不然tot在递归时候可能改变。还要注意一下就是我的广义SAM板子中间有clone的地方但是可能没看出来，可以在solve()函数里再每次对lst节点更新endpos。
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 998244353;
string str[maxn];
struct SegmentTree {
#define lson t[rt].ls
#define rson t[rt].rs
#define mid ((l + r) >> 1)
struct Node {
int ls, rs;
pii mx;
};
Node t[maxn << 4];
int tot = 0;
void push_up(int rt) {
if (t[lson].mx.first != t[rson].mx.first)
t[rt].mx = max(t[lson].mx, t[rson].mx);
else
t[rt].mx = min(t[lson].mx, t[rson].mx);
}
int Merge(int x, int y, int l, int r) {
if (!x || !y) return x | y;
int now = ++tot;
if (l == r) {
t[now].mx = t[x].mx;
t[now].mx.first += t[y].mx.first;
return now;
}
t[now].ls = Merge(t[x].ls, t[y].ls, l, mid);
t[now].rs = Merge(t[x].rs, t[y].rs, mid + 1, r);
push_up(now);
return now;
}
void modify(int&rt, int l, int r, int pos) {
if (!rt) rt = ++tot;
if (l == r) {
t[rt].mx.first++;
t[rt].mx.second = l;
return;
}
if (pos <= mid) modify(lson, l, mid, pos);
else modify(rson, mid + 1, r, pos);
push_up(rt);
}
pii query(int rt, int l, int r, int p, int q) {
if (!rt) return pii(0, 0);
if (p <= l && r <= q) return t[rt].mx;
if (q <= mid) return query(lson, l, mid, p, q);
if (p > mid) return query(rson, mid + 1, r, p, q);
pii res1 = query(lson, l, mid, p, mid), res2 = query(rson, mid + 1, r, mid + 1, q);
if (res1.first != res2.first) return max(res1, res2);
return min(res1, res2);
}
} seg;
int root[maxn], n;
struct SAM {
int tot, fa[maxn], len[maxn], c[maxn][26];
SAM() { tot = 1; }
int extend(char chr, int last, int id) {
int ch = chr - 'a';
if (c[last][ch]) {
int p = last, x = c[p][ch];
if (len[p] + 1 == len[x]) {
return x;
}
else {
int y = ++tot;
len[y] = len[p] + 1;
memcpy(c[y], c[x], sizeof c[y]);
while (p && c[p][ch] == x)
c[p][ch] = y, p = fa[p];
fa[y] = fa[x], fa[x] = y;
return y;
}
}
int z = ++tot, p = last;
len[z] = len[last] + 1;
while (p && !c[p][ch])
c[p][ch] = z, p = fa[p];
if (!p)
fa[z] = 1;
else {
int x = c[p][ch];
if (len[p] + 1 == len[x])
fa[z] = x;
else {
int y = ++tot;
len[y] = len[p] + 1;
memcpy(c[y], c[x], sizeof c[y]);
while (p && c[p][ch] == x)
c[p][ch] = y, p = fa[p];
fa[y] = fa[x], fa[z] = fa[x] = y;
}
}
return z;
}
} sam;
vector
int fa[maxn][21], lg[maxn], dep[maxn];
int to[maxn], mxlen[maxn], nowlen;
void dfs(int u, int deep) {
if (u == 2)
int debug = 0;
dep[u] = deep;
for (int i = 1; i <= lg[dep[u]]; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (auto v : G[u]) {
fa[v][0] = u;
dfs(v, deep + 1);
root[u] = seg.Merge(root[u], root[v], 1, n);
}
}
void solve() {
string S; cin >> S;
cin >> n;
for (int i = 1; i <= n; i++) {
int lst = 1;
cin >> str[i];
for (int j = 1; j <= str[i].length(); j++)
lst = sam.extend(str[i][j - 1], lst, i), seg.modify(root[lst], 1, n, i);
}
for (int i = 2; i <= sam.tot; i++)
G[sam.fa[i]].push_back(i);
dfs(1, 0);
int p = 1;
for (int i = 1; i <= S.length(); i++) {
while (p > 1 && !sam.c[p][S[i - 1] - 'a']) p = sam.fa[p], nowlen = sam.len[p];
if (sam.c[p][S[i - 1] - 'a']) p = sam.c[p][S[i - 1] - 'a'], nowlen++;
to[i] = p, mxlen[i] = nowlen;
}
int q; cin >> q;
while (q--) {
int L, R, l, r; cin >> L >> R >> l >> r;
if (r - l + 1 > mxlen[r]) {
cout << L << " " << 0 << "\n";
continue;
}
int u = to[r];
for (int i = lg[dep[u]]; i >= 0; i--) {
int v = fa[u][i];
if (sam.len[v] >= r - l + 1)
u = v;
}
pii res = seg.query(root[u], 1, n, L, R);
if (res.first == 0) res.second = L;
cout << res.second << " " << res.first << "\n";
}
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
for (int i = 2; i < maxn; i++) lg[i] = lg[i >> 1] + 1;
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
### 23CCPC哈尔滨C
https://qoj.ac/contest/1412/problem/7748
给定字符串S，每个前缀有权值 $w[i]$， 给定字符串T，多次询问，每次询问T的子串[l,r], 求子串的权值。权值定义为，每个S的前缀在该字符串的出现次数乘该前缀的$w[i]$
思路是考虑用Z函数求出T的每个前缀跟S的LCP后，就可以列出来暴力的表达式 $\sum_{i = l}^r sumw[min(r - i + 1, z[i])]$. 考虑对该式子化简，有min，显然可以考虑去找一下分界线。即找到最左边的位置，满足该位置跟S的LCP会越过询问的右端点，在分界点左边，min都是取z[i]，所以直接用前缀和就可以一下得到。在右边，既然这个mid的LCP越过了左端点，所以这部分的答案相当于 S 的长为r-mid+1的前缀对应的答案，所以可以考虑预处理一下S的所有前缀，对应的答案，可以用kmp的border累加递推一下。
至于找最左边的mid,可以用st表存每个位置的LCP，然后二分，如果从询问左端点l到mid里的LCP最大值越过右端点则合法，可以继续往左边取。
补一下错误的思路，赛时一直在想这个东西能不能用SAM来维护，因为看到询问的子串，就想着去跳parent树到对应节点，想看能不能从子树里判断那个节点有多少前缀。但是发现不太行，子树中没有那种性质，硬要做的话应该只能对于每个前缀的对应节点，根据endpos集合，判断出现在了多少个询问区间里对应加贡献，但是这样复杂度有问题，不能硬做，所以还是只能用上面那种题解的方法。
点击查看代码
#include
#define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 4e5 + 10;
const int mod = 998244353;
int w[maxn], sumw[maxn], sumww[maxn], sumwz[maxn], z[maxn];
int st[maxn][21], lg[maxn];
int query(int l, int r) {
int k = lg[r - l + 1];
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
struct exKMP {
int z[maxn];
void get_z(string& c) {
int len = c.length();
int p = 0, k = 1, l;
z[0] = len;
while (p + 1 < len && c[p] == c[p + 1])
p++;
z[1] = p;
for (int i = 2; i < len; i++) {
p = k + z[k] - 1;
l = z[i - k];
if (i + l <= p)
z[i] = l;
else {
int j = max(0ll, p - i + 1);
while (i + j < len && c[i + j] == c[j])
j++;
z[i] = j;
k = i;
}
}
}
} Z;
int get(int L, int R) { //找区间L,R内最小的能匹配到至少R的点
int l = L, r = R, ans = R + 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (query(L, mid) >= R) ans = mid, r = mid - 1;
else l = mid + 1;
}
return ans;
}
int nxt[maxn], pre[maxn];
void getnxt(string str) { // 得到str的next数组，next数组为对应位置的最长border
nxt[0] = 0;
for (int i = 1, j = 0; i < str.length(); i++) {
while (j && str[i] != str[j])
j = nxt[j - 1];
if (str[i] == str[j])
j++;
nxt[i] = j;
pre[i + 1] += pre[j];
}
}
void solve() {
int n, m; cin >> n >> m;
string S, T; cin >> S >> T;
for (int i = 1; i <= n; i++) {
cin >> w[i];
sumw[i] = sumw[i - 1] + w[i];
sumww[i] = sumww[i - 1] + sumw[i];
}
int lens = S.length(), lent = T.length();
string tem = S + '#' + T;
Z.get_z(tem);
for (int i = 1; i <= lent; i++)
z[i] = Z.z[lens + i], sumwz[i] = sumwz[i - 1] + sumw[z[i]], st[i][0] = i + z[i] - 1;
for (int j = 1; j < 21; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
for (int i = 0; i <= n; i++)
pre[i] = w[i];
getnxt(S);
for (int i = 1; i <= lent; i++)
pre[i] += pre[i - 1];
while (m--) {
int l, r; cin >> l >> r;
int pos = get(l, r);
int ans = sumwz[pos - 1] - sumwz[l - 1] + pre[r + 1 - pos];
cout << ans << "\n";
}
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
for (int i = 2; i < maxn; i++)
lg[i] = lg[i >> 1] + 1;
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
CF700E
一个关键的地方在于，判断parent树上一个串有没有在儿子结点的串里出现过，这个就可以利用endpos是否在对应区间里出现过来判断，所以套路地用SAM的parent树上动态开点权值线段树合并后就可以DP解决。
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 5e5 + 10;
const int mod = 998244353;
struct SegmentTree {
struct Node {
int ls, rs, sum;
};
Node t[maxn << 5];
int tot = 0;
#define lson t[rt].ls
#define rson t[rt].rs
#define mid ((l + r) >> 1)
void push_up(int rt) {t[rt].sum = t[lson].sum + t[rson].sum;}
void modify(int& rt, int l, int r, int pos) {
if (!rt) rt = ++tot;
if (l == r) {
t[rt].sum++;
return;
}
if (pos <= mid) modify(lson, l, mid, pos);
else modify(rson, mid + 1, r, pos);
push_up(rt);
}
int Merge(int x, int y, int l, int r) {
if (!x || !y) return x | y;
int now = ++tot;
if (l == r) {
t[now].sum = t[x].sum + t[y].sum;
return now;
}
t[now].ls = Merge(t[x].ls, t[y].ls, l, mid);
t[now].rs = Merge(t[x].rs, t[y].rs, mid + 1, r);
push_up(now);
return now;
}
int query(int rt, int l, int r, int p, int q) {
if (p > r || q < l) return 0;
if (p <= l && r <= q) return t[rt].sum;
return query(lson, l, mid, p, q) + query(rson, mid + 1, r, p, q);
}
} seg;
struct SAM {
int tot, lst, len[maxn << 1], fa[maxn << 1], c[maxn << 1][27];
int cnt[maxn << 1], endpos[maxn];
SAM() { tot = lst = 1; }
void extend(char ch) {
int x = ch - 'a', cur = ++tot, u;
cnt[cur] = 1, len[cur] = len[lst] + 1;
for (u = lst; u && !c[u][x]; u = fa[u]) c[u][x] = cur;
if (!u) fa[cur] = 1;
else {
int v = c[u][x];
if (len[v] == len[u] + 1) fa[cur] = v;
else {
int clone = ++tot;
len[clone] = len[u] + 1, fa[clone] = fa[v];
memcpy(c[clone], c[v], sizeof c[v]); // 时间复杂度在这个地方
for (; u && c[u][x] == v; u = fa[u])
c[u][x] = clone;
fa[cur] = fa[v] = clone;
}
}
lst = cur;
}
} sam;
vector
int root[maxn], n, dp[maxn];
void dfs(int u) {
for (auto v : G[u]) {
dfs(v);
root[u] = seg.Merge(root[u], root[v], 1, n);
if (!sam.endpos[u])
sam.endpos[u] = sam.endpos[v];
}
}
int top[maxn];
void dfs2(int u) {
dp[u] = max(dp[u], 1);
for (auto v : G[u]) {
// 如果u 在 v 里出现2次，dp[v] 可以为 dp[u] + 1
int pos = sam.endpos[v];
int l = pos - sam.len[v] + sam.len[top[u]], r = pos - 1;
if (u == 1) {
dp[v] = 1;
top[v] = v;
} else if (seg.query(root[top[u]], 1, n, l, r)) {
dp[v] = dp[u] + 1;
top[v] = v;
} else {
dp[v] = dp[u];
top[v] = top[u];
}
dfs2(v);
}
}
void solve() {
cin >> n;
string str; cin >> str;
for (int i = 1; i <= n; i++)
sam.extend(str[i - 1]), seg.modify(root[sam.lst], 1, n, i), sam.endpos[sam.lst] = i;
for (int i = 2; i <= sam.tot; i++)
G[sam.fa[i]].push_back(i), top[i] = i;
dfs(1);
dfs2(1);
int ans = 0;
for (int i = 2; i <= sam.tot; i++)
ans = max(ans, dp[i]);
cout << ans << "\n";
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
CF204E
https://codeforces.com/problemset/problem/204/E
这题做的太痛苦了，前面由于读错题了直接看题解，导致写完调了很久bug才发现读错题了。
题意:给 \(n\) 个字符串，对于每个字符串，求有多少个子串，满足这个子串在 \(n\) 个字符串里至少 \(k\) 个串中出现过。
一开始我读题以为是在 \(n\) 个串里累计出现 \(k\) 次即可，这样的话就不用什么线段树合并，直接累加就行，但是因为是在至少 \(k\) 个出现过，所以一个串只能对广义SAM里面的相关结点贡献1，不能重复贡献。所以做法就是建个广义SAM，然后在extend的过程中，给对应结点的线段树单点赋值1，最后跑个线段树合并，就看可以求出广义SAM里每个结点都在哪些串出现过。然后统计子串，则再把原串在SAM上运行一下，对于每个前缀对应的 to[i], 看出现次数是否达到 \(k\), 达到了则parent链上所有后缀都能达到，所以贡献加 len[to[i]]， 没达到则倍增跳到第一个满足条件的后缀，再去加对应长度。
在wa了好久之后，发现原来之前一直背的李队的倍增板子好像有问题，不考虑log，直接暴力枚举20可以过，sad.
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 5e5 + 10;
const int mod = 998244353;
string str[maxn];
struct SegmentTree {
struct Node {
int ls, rs, sum;
};
#define lson t[rt].ls
#define rson t[rt].rs
#define mid ((l + r) >> 1)
Node t[maxn << 4];
int tot = 0;
void push_up(int rt) {t[rt].sum = t[lson].sum + t[rson].sum;}
int Merge(int x, int y, int l, int r) {
if (!x || !y) return x | y;
int now = ++tot;
if (l == r) {
t[now].sum = t[x].sum | t[y].sum;
return now;
}
t[now].ls = Merge(t[x].ls, t[y].ls, l, mid);
t[now].rs = Merge(t[x].rs, t[y].rs, mid + 1, r);
push_up(now);
return now;
}
void modify(int& rt, int l, int r, int pos) {
if (!rt) rt = ++tot;
if (l == r) {
t[rt].sum = 1;
return;
}
if (pos <= mid) modify(lson, l, mid, pos);
else modify(rson, mid + 1, r, pos);
push_up(rt);
}
int query(int rt, int l, int r, int p, int q) {
if (q < l || p > r || !rt) return 0;
if (p <= l && r <= q) return t[rt].sum;
return query(lson, l, mid, p, q) + query(rson, mid + 1, r, p , q);
}
} seg;
int root[maxn];
struct SAM{
int tot, fa[maxn], len[maxn], c[maxn][26];
SAM(){tot = 1;}
int extend(char chr, int last){
int ch = chr - 'a';
if (c[last][ch]) {
int p = last, x = c[p][ch];
if (len[p] + 1 == len[x]) return x;
else {
int y = ++tot;
len[y] = len[p] + 1;
memcpy(c[y], c[x], sizeof c[y]);
while (p && c[p][ch] == x)
c[p][ch] = y, p = fa[p];
fa[y] = fa[x], fa[x] = y;
return y;
}
}
int z = ++tot, p = last;
len[z] = len[last] + 1;
while (p && !c[p][ch])
c[p][ch] = z, p = fa[p];
if (!p) fa[z] = 1;
else {
int x = c[p][ch];
if (len[p] + 1 == len[x]) fa[z] = x;
else {
int y = ++tot;
len[y] = len[p] + 1;
memcpy(c[y], c[x], sizeof c[y]);
while (p && c[p][ch] == x)
c[p][ch] = y, p = fa[p];
fa[y] = fa[x], fa[z] = fa[x] = y;
}
}
return z;
}
} sam;
vector
int fa[maxn][21], n, k;
int totcnt[maxn];
void dfs(int u, int deep) {
for (int i = 1; i < 21; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (auto v : G[u]) {
fa[v][0] = u;
dfs(v, deep + 1);
root[u] = seg.Merge(root[u], root[v], 1, n);
}
totcnt[u] = seg.t[root[u]].sum;
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> str[i];
int lst = 1;
for (int j = 1; j <= str[i].length(); j++) {
lst = sam.extend(str[i][j - 1], lst);
seg.modify(root[lst], 1, n, i);
}
}
for (int i = 2; i <= sam.tot; i++)
G[sam.fa[i]].push_back(i);
dfs(1, 0);
for (int i = 1; i <= n; i++) {
ll ans = 0, p = 1;
for (int j = 1; j <= str[i].length(); j++) {
p = sam.c[p][str[i][j - 1] - 'a'];
if (totcnt[p] >= k)
ans += sam.len[p];
else {
int u = p;
for (int jj = 20; jj >= 0; jj--) {
int v = fa[u][jj];
if (!v) continue;
if (totcnt[v] < k) u = v;
}
if (totcnt[u] < k) u = fa[u][0];
ans += sam.len[u];
}
}
cout << ans << " \n"[i == n];
}
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
CF557E
定义半回文串是奇数位置要求回文的字符串，给定字符串求字典序第k小的半回文子串。前面 \(O(n^2)\) 的dp没想到怎么判断所有子串是不是半回文的，其实这个判断出来之后就变成类似弦论那题，在trie树上二分出字典序第k大的字符串是什么。做法是先求出每个结点代表的字符串个数，再累加求个子树和，然后在trie树上减是减当前结点的个数，判断往哪走是用的子树和那个数组，每走一步输出转移边的对应字符即可。
点击查看代码
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 5e3 + 10;
const int maxm = maxn * maxn / 2;
const int mod = 998244353;
int dp[maxn][maxn];
struct TRIE {
int tot = 1, c[maxm][2], siz[maxm], sum[maxm];
int insert(int p, string str) {
for (auto ch : str) {
if (!c[p][ch - 'a']) c[p][ch - 'a'] = ++tot;
p = c[p][ch - 'a'];
}
siz[p]++;
return p;
}
void dfs(int u) {
sum[u] = siz[u];
for (int i = 0; i < 2; i++) {
if (c[u][i])
dfs(c[u][i]), sum[u] += sum[c[u][i]];
}
}
void solve(int k) {
int p = 1;
while(k) {
int ls = sum[c[p][0]];
k -= siz[p];
if (k <= 0) return;
if (k <= ls) {
cout << 'a';
p = c[p][0];
} else {
cout << 'b';
k -= ls;
p = c[p][1];
}
if (!p) return;
}
}
} trie;
void solve() {
string str; cin >> str;
int k; cin >> k;
int n = str.length();
for (int len = 1; len <= n; len++)
for (int i = 1; i <= n; i++) {
int l = i, r = i + len - 1;
if (r - l < 4) dp[l][r] = str[l - 1] == str[r - 1];
else dp[l][r] = (str[l - 1] == str[r - 1]) && dp[l + 2][r - 2];
}
// for (int i = 1; i <= n; i++)
// for (int j = i; j <= n; j++) {
// if (dp[i][j])
// trie.insert(1, str.substr(i - 1, j - i + 1));
// }
for (int i = 1; i <= n; i++) {
int p = 1;
string tem;
for (int j = i; j <= n; j++) {
tem.push_back(str[j - 1]);
if (dp[i][j])
p = trie.insert(p, tem), tem.clear();
}
}
trie.dfs(1);
trie.solve(k);
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
CF547E Mike and Friends
https://codeforces.com/contest/547/problem/E
很经典的多方法题，很早之前写过ac自动机fail树dfn序上建可持久化线段树的解法，但是自从学了SAM后满脑子都是SAM，所以回来补了一下用广义SAM的做法，调的头皮发麻后才发现板子错了，区间查询忘记返回了，所以一直t。
题意是给 \(n\) 个字符串，每次询问给定 \(l, r, k\)， 问第 \(k\) 个串在第[l,r]区间的串里总共出现多少次。那么显然可以建一个广义sam，然后预处理每个串在上面的结点处，查询对应节点拥有对应区间多少串的贡献。所以可以线段树合并，权值线段树搞一下，dfs。这里我算是搞明白之前一直不太清楚的，线段树合并的两种写法，一种是每次merge都新建一个节点++cnt，这样写可以保留所有线段树的信息。另一种写法是把第二个结点合并到第一个结点，返回u，但是全部合并后，会破坏之前的线段树的结构，但是比较省空间，所以离线后可以第二种写法在对应结点查询，查询后这个树没用了，就给父节点乱合并就行。
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 5e5 + 10;
const int mod = 998244353;
struct SegmentTree {
struct Node {
int ls, rs, sum;
};
#define lson t[rt].ls
#define rson t[rt].rs
#define mid ((l + r) >> 1)
Node t[4000000];
int tot = 0;
void push_up(int rt) {t[rt].sum = t[lson].sum + t[rson].sum;}
int Merge(int x, int y, int l, int r) {
if (!x || !y) return x | y;
if (l == r) {
t[x].sum += t[y].sum;
return x;
}
t[x].ls = Merge(t[x].ls, t[y].ls, l, mid);
t[x].rs = Merge(t[x].rs, t[y].rs, mid + 1, r);
push_up(x);
return x;
}
void modify(int& rt, int l, int r, int pos) {
if (!rt) rt = ++tot;
if (l == r) {
t[rt].sum++;
return;
}
if (pos <= mid) modify(lson, l, mid, pos);
else modify(rson, mid + 1, r, pos);
push_up(rt);
}
ll query(int rt, int l, int r, int p, int q) {
if (!rt || p > r || q < l) return 0;
if (p <= l && r <= q) return t[rt].sum;
return query(lson, l, mid, p, q) + query(rson, mid + 1, r, p , q);
}
} seg;
struct SAM{
int tot, fa[maxn], len[maxn], c[maxn][26];
SAM(){tot = 1;}
int extend(char chr, int last){
int ch = chr - 'a';
if (c[last][ch]) {
int p = last, x = c[p][ch];
if (len[p] + 1 == len[x]) return x;
else {
int y = ++tot;
len[y] = len[p] + 1;
memcpy(c[y], c[x], sizeof c[y]);
while (p && c[p][ch] == x)
c[p][ch] = y, p = fa[p];
fa[y] = fa[x], fa[x] = y;
return y;
}
}
int z = ++tot, p = last;
len[z] = len[last] + 1;
while (p && !c[p][ch])
c[p][ch] = z, p = fa[p];
if (!p) fa[z] = 1;
else {
int x = c[p][ch];
if (len[p] + 1 == len[x]) fa[z] = x;
else {
int y = ++tot;
len[y] = len[p] + 1;
memcpy(c[y], c[x], sizeof c[y]);
while (p && c[p][ch] == x)
c[p][ch] = y, p = fa[p];
fa[y] = fa[x], fa[z] = fa[x] = y;
}
}
return z;
}
} sam;
int to[maxn], root[maxn], n, q, ans[500010];
struct Node {
int l, r, id;
};
vector
vector
void dfs(int u) {
for (auto v : G[u]) {
dfs(v);
root[u] = seg.Merge(root[u], root[v], 1, n);
}
for (auto [l, r, id] : query[u])
ans[id] = seg.query(root[u], 1, n, l, r);
}
void solve() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
string str; cin >> str;
int lst = 1;
for (auto ch : str) {
lst = sam.extend(ch, lst);
seg.modify(root[lst], 1, n, i);
}
to[i] = lst;
}
for (int i = 2; i <= sam.tot; i++)
G[sam.fa[i]].push_back(i);
for (int i = 1; i <= q; i++) {
int l, r, k; cin >> l >> r >> k;
query[to[k]].push_back(Node{l, r, i});
}
dfs(1);
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
23沈阳D Dark LaTeX vs. Light LaTeX
https://qoj.ac/contest/1449/problem/7780
题意是给两个字符串S和T，要求各选一个子串拼接后是一个平方串，问有多少种选法。平方串定义为字符串长度是偶数，且前一半等于后一半。
范队很快给出了一个方向，枚举S的一个子串[l,r]，那么对于它的border，去找夹在这两端相等的串里面的小串是否在T串里出现。不过这样做枚举子串 \(O(n^2)\), 再暴力跳border还要 \(O(n)\)， 所以会T。想了很久，转化了一下思路，去枚举中间那个串，看两端能拼接多少个相同的串，一开始以为有单调性，后面发现没有。因为上次的字符串题是z函数，所以这里又灵机一动，看看z函数有没有用，忽然就发现了，求出S的z函数后，每个右端点，就可以对连续的一段右端点相同的子串有贡献，这样做就是 \(O(n)\)的了。然后就可以求出，每个串的贡献，枚举所有子串，贡献乘T串里对应部分的出现次数。但是发现这题有点卡哈希，单哈希会wa，双哈希又T了。于是贡献了不少罚时后，最后被迫换方法，在范队指示下，再用一次z函数来预处理出S的所有子串在T里的出现次数。这里还是用到了差分，相当于枚举S的所有后缀，跟T拼起来，枚举T的位置，就可以有lcp那些子串出现过，差分一下就得到一个串所有子串在另一个串的出现次数数组，最终总复杂度是 \(O(n^2)\) 的。(赛后看榜发现这题现场只过20个那里，爽了)
补充：后来忽然想起来求一个串所有子串在另一个串的出现次数，这个也是SAM的经典应用，于是补了一下用SAM求cnt数组的做法，wa和re好几次，最后还是看着qoj的数据才调出来，看来还是不太熟练。做法就是对T串建SAM，然后用S串在上面跑，而且要注意跑的时候得用一个变量len维护一下当前前缀匹配上的最大长度，然后一路跳fail树，得到对应子串的次数为SAM上对应结点的出现次数。
点击查看代码
#include
// #define int long long
#define ll long long
#define db double
#define i128 __int128_t
#define pii pair
using namespace std;
const int maxn = 5e3 + 10;
struct exKMP {
int z[100010];
void get_z(string& c) {
int len = c.length();
int p = 0, k = 1, l;
z[0] = len;
while (p + 1 < len && c[p] == c[p + 1])
p++;
z[1] = p;
for (int i = 2; i < len; i++) {
p = k + z[k] - 1;
l = z[i - k];
if (i + l <= p)
z[i] = l;
else {
int j = max(0, p - i + 1);
while (i + j < len && c[i + j] == c[j])
j++;
z[i] = j;
k = i;
}
}
}
} Z;
int sub[maxn][maxn];
int cnt[maxn][maxn];
void get_cnt(string s, string t) { // cnt[i][j] : S [i, j] 在 T 的出现次数
int n = s.length();
for (int i = 1; i <= n; i++) {
string tem = s.substr(i - 1) + '#' + t;
Z.get_z(tem);
for (int j = n - i + 2; j < tem.length(); j++) {
if (Z.z[j]) {
cnt[i][i]++;
cnt[i][i + Z.z[j]]--;
}
}
}
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
cnt[i][j] += cnt[i][j - 1];
int p = 1, len = 0; //SAM求法
for (int i = 1; i <= n; i++) {
while (p > 1 && !sam.c[p][s[i - 1] - 'a']) p = sam.fa[p], len = sam.len[p];
if (sam.c[p][s[i - 1] - 'a']) p = sam.c[p][s[i - 1] - 'a'], len++;
int u = p;
for (int j = len; j >= 1; j--) {
if (j <= sam.len[sam.fa[u]]) u = sam.fa[u];
cnt[i - j + 1][i] = sam.cnt[u];
}
}
}
ll cal(string s, string t, int id) {
int n = s.length(), m = t.length();
ll ans = 0;
// cout << "same" << ans << endl;
get_cnt(s, t);
if (id == 0) {
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
ans += cnt[i][j];
}
for (int i = 1; i <= n; i++) {
string str2 = s.substr(i - 1);
Z.get_z(str2);
for (int j = 3; j <= str2.length(); j++) {
int mxlen = min(Z.z[j - 1], j - 1);
if (!mxlen) continue;
// 右端点在 j - 1, 左端点在 2 到 mxlen + 1
sub[i - 1 + j - 1][i - 1 + 2]++;
sub[i - 1 + j - 1][i - 1 + mxlen + 1 + 1]--;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) {
sub[i][j] += sub[i][j - 1];
if (sub[i][j] > 0) {
ans += sub[i][j] * cnt[j][i];
// cout << "l, r = " << j << " " << i << endl;
}
}
return ans;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string s, t;
cin >> s >> t;
ll res = cal(s, t, 0);
memset(sub, 0, sizeof sub);
memset(cnt, 0, sizeof cnt);
res += cal(t, s, 1);
cout << res << endl;
return 0;
}
ZJOI 诸神眷顾的幻想乡
https://www.luogu.com.cn/problem/P3346
这个是广义SAM的板，无意间发现了给出trie树怎么在线建广义SAM的方法，其实也就是dfs一下，然后记录过程里的lst指针，回溯的时候直接从之前的lst开始接着往下建，很自然的想法。
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 3e6 + 10;
const int mod = 998244353;
vector
char ch[maxn];
struct SAM{
int tot, fa[maxn], len[maxn], c[maxn][11];
SAM(){tot = 1;}
int extend(char chr, int last){
int ch = chr - '0';
if (c[last][ch]) {
int p = last, x = c[p][ch];
if (len[p] + 1 == len[x]) return x;
else {
int y = ++tot;
len[y] = len[p] + 1;
memcpy(c[y], c[x], sizeof c[y]);
while (p && c[p][ch] == x)
c[p][ch] = y, p = fa[p];
fa[y] = fa[x], fa[x] = y;
return y;
}
}
int z = ++tot, p = last;
len[z] = len[last] + 1;
while (p && !c[p][ch])
c[p][ch] = z, p = fa[p];
if (!p) fa[z] = 1;
else {
int x = c[p][ch];
if (len[p] + 1 == len[x]) fa[z] = x;
else {
int y = ++tot;
len[y] = len[p] + 1;
memcpy(c[y], c[x], sizeof c[y]);
while (p && c[p][ch] == x)
c[p][ch] = y, p = fa[p];
fa[y] = fa[x], fa[z] = fa[x] = y;
}
}
return z;
}
} sam;
void dfs(int u, int f, int lst) {
lst = sam.extend(ch[u], lst);
for (auto v : G[u])
if (v != f)
dfs(v, u, lst);
}
void solve() {
int n, c; cin >> n >> c;
for (int i = 1; i <= n; i++) cin >> ch[i];
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (G[i].size() == 1) leaf.push_back(i);
}
for (auto u : leaf)
dfs(u, 0, 1);
ll ans = 0;
for (int i = 2; i <= sam.tot; i++)
ans += sam.len[i] - sam.len[sam.fa[i]];
cout << ans << "\n";
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
CF1037 H. Security
https://codeforces.com/problemset/problem/1037/H
32伯分，拿下！这题的题意是，给定字符串S，多次询问，每次给定区间[l,r]和询问串T，问原串S在区间[l,r]内恰好字典序比T大的串是什么。
这里感觉最主要是想到有个贪心，答案肯定是询问串的最长前缀往后塞一个字符，满足这样的串位于询问区间内。所以关键在于怎么判断SAM的一个节点在不在询问区间，这里就是套路的SAM上对endpos建线段树合并，然后就可以把询问串放上面跑，根据当前匹配的长度询问对应节点的endpos是否在[l+len,r]内有值，就知道对应区间内是否有一个那样的节点。然后只走这样的节点，看看最长能匹配多少，再枚举往后塞一个字符，是否还是符合条件的节点，即可。
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 4e5 + 10;
const int mod = 998244353;
struct SegmentTree {
struct Node {
int ls, rs, sum;
};
#define lson t[rt].ls
#define rson t[rt].rs
#define mid ((l + r) >> 1)
Node t[maxn << 5];
int tot = 0;
void push_up(int rt) {t[rt].sum = t[lson].sum + t[rson].sum;}
int Merge(int x, int y, int l, int r) { //如果可以破坏信息，就不要++tot，返回x
if (!x || !y) return x | y;
int now = ++tot;
if (l == r) {
t[now].sum = t[x].sum + t[y].sum;
return now;
}
t[now].ls = Merge(t[x].ls, t[y].ls, l, mid);
t[now].rs = Merge(t[x].rs, t[y].rs, mid + 1, r);
push_up(now);
return now;
}
void modify(int& rt, int l, int r, int pos) {
if (!rt) rt = ++tot;
if (l == r) {
t[rt].sum++;
return;
}
if (pos <= mid) modify(lson, l, mid, pos);
else modify(rson, mid + 1, r, pos);
push_up(rt);
}
int query(int rt, int l, int r, int p, int q) {
if (!rt || p > r || q < l) return 0;
if (p <= l && r <= q) return t[rt].sum;
return query(lson, l, mid, p, q) + query(rson, mid + 1, r, p , q);
}
} seg;
struct SAM {
int tot, lst, len[maxn << 1], fa[maxn << 1], c[maxn << 1][27];
int cnt[maxn << 1];
SAM() { tot = lst = 1; }
int id[maxn << 1], tong[maxn];
void topo() { //基数排序后, 逆序枚举为拓扑序
for (int i = 1; i <= tot; i++) tong[len[i]]++;
for (int i = 1; i <= tot; i++) tong[i] += tong[i - 1];
for (int i = tot; i; i--) id[tong[len[i]]--] = i;
}
void extend(char ch) {
int x = ch - 'a', cur = ++tot, u;
cnt[cur] = 1, len[cur] = len[lst] + 1;
for (u = lst; u && !c[u][x]; u = fa[u]) c[u][x] = cur;
if (!u) fa[cur] = 1;
else {
int v = c[u][x];
if (len[v] == len[u] + 1) fa[cur] = v;
else {
int clone = ++tot;
len[clone] = len[u] + 1, fa[clone] = fa[v];
memcpy(c[clone], c[v], sizeof c[v]); // 时间复杂度在这个地方
for (; u && c[u][x] == v; u = fa[u])
c[u][x] = clone;
fa[cur] = fa[v] = clone;
}
}
lst = cur;
}
} sam;
int root[maxn], mn[maxn];
void solve() {
string str; cin >> str;
int n = str.length();
for (int i = 1; i <= n; i++) {
sam.extend(str[i - 1]);
seg.modify(root[sam.lst], 1, n, i);
}
sam.topo();
for (int i = sam.tot; i; i--) {
int u = sam.id[i], v = sam.fa[u];
root[v] = seg.Merge(root[v], root[u], 1, n);
}
int q; cin >> q;
while (q--) {
int l, r; string s;
cin >> l >> r >> s;
int p = 1, len = 0;
for (int i = 0; i <= s.length(); i++) mn[i] = 0;
for (auto ch : s) {
for (int i = ch - 'a' + 1; i < 26; i++) {
if (sam.c[p][i]) {
int u = sam.c[p][i];
if (seg.query(root[u], 1, n, l + len, r)) {
mn[len] = i;
break;
}
}
}
if (!sam.c[p][ch - 'a']) break;
int u = sam.c[p][ch - 'a'];
if (seg.query(root[u], 1, n, l + len, r)) {
p = sam.c[p][ch - 'a'];
len++;
} else break;
}
if (len == s.length()) {
int flag = 0;
for (int i = 0; i < 26; i++) {
if (sam.c[p][i]) {
int u = sam.c[p][i];
if (seg.query(root[u], 1, n, l + len, r)) {
cout << s << (char)('a' + i) << "\n";
flag = 1;
break;
}
}
}
if (flag) continue;
}
int flag = 0;
for (int i = len; i >= 0; i--) {
if (mn[i]) {
cout << s.substr(0, i) << (char)('a' + mn[i]) << "\n";
flag = 1;
break;
}
}
if (!flag) cout << -1 << "\n";
}
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
CF1207 G. Indie Album
https://codeforces.com/problemset/problem/1207/G
真红温了！！最后傻逼的，调试时候把每个地方树状数组查询了一下，忘记删掉，一直T，卡了好久才想起来，前面也是细节特别多。
题意是，两种操作，一个是新建一个字符串，一个是把之前某个字符串后面加一个字符后作为新的版本字符串，其实也就是给一个trie树。多次询问，每次询问给一个询问串和id，问这个询问串在id那个串里出现几次。
很巧妙的用了一个trie树上dfs的做法。做法是对询问串建一个acam，把文本串放上面跑，根据acam的fail树性质，等价于每跑到一个节点，fail到根的链上所有串都作为当前的后缀出现，所以反过来，就是每个询问串在acam的节点子树里面，文本串经过了多少次。然后关键利用了trie树，所以在trie树上dfs，每次用树状数组单点修改匹配到的节点dfs序出现次数加一，询问离线挂到对应acam节点上，走完了就查询对应询问的子树区间权值。细节比较多，挑了很久。
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 5e5 + 10;
const int mod = 998244353;
struct ACM {
int c[maxn][26], fail[maxn], tot;
queue
int insert(string& str) {
int len = str.length(), now = 0;
for (int i = 0; i < len; i++) {
int v = str[i] - 'a';
if (!c[now][v]) c[now][v] = ++tot;
now = c[now][v];
}
return now;
}
void build() {
for (int i = 0; i < 26; i++)
if (c[0][i])
q.push(c[0][i]), fail[c[0][i]] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < 26; i++) {
if (c[u][i])
fail[c[u][i]] = c[fail[u]][i], q.push(c[u][i]);
else c[u][i] = c[fail[u]][i];
}
}
}
} acm;
struct BIT {
int t[maxn];
int lowbit(int x) { return x & -x; }
void update(int i, int x) {
// i++;
for (int pos = i; pos < maxn; pos += lowbit(pos))
t[pos] += x;
}
int query(int i) {
// i++;
int res = 0;
for (int pos = i; pos; pos -= lowbit(pos))
res += t[pos];
return res;
}
} bit;
vector
vector
int L[maxn], R[maxn], ncnt, ans[maxn], to[maxn];
struct TRIE {
int c[maxn][26], tot;
int insert(int p, char ch) {
if (!c[p][ch - 'a'])
c[p][ch - 'a'] = ++tot;
p = c[p][ch - 'a'];
return p;
}
void dfs(int u, int p) {
for (auto [qid, acmnode] : query[u])
ans[qid] = bit.query(R[acmnode]) - bit.query(L[acmnode] - 1);
for (int i = 0; i < 26; i++) {
int v = c[u][i];
if (!v) continue;
bit.update(L[acm.c[p][i]], 1);
dfs(v, acm.c[p][i]);
bit.update(L[acm.c[p][i]], -1);
}
}
} trie;
void dfs(int u) {
L[u] = ++ncnt;
for (auto v : G[u])
dfs(v);
R[u] = ncnt;
}
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
int op; cin >> op;
if (op == 1) {
char ch; cin >> ch;
to[i] = trie.insert(0, ch);
} else {
int id; char ch;
cin >> id >> ch;
to[i] = trie.insert(to[id], ch);
}
}
int q; cin >> q;
for (int i = 1; i <= q; i++) {
int id; string str;
cin >> id >> str;
query[to[id]].push_back(pii(i, acm.insert(str)));
}
acm.build();
for (int i = 1; i <= acm.tot; i++)
G[acm.fail[i]].push_back(i);
dfs(0);
trie.dfs(0, 0);
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
CF1437 G.Death DBMS
https://codeforces.com/problemset/problem/1437/G
给定 \(n\) 个字符串，两种操作，一是修改一个串的权值，二是给定一个询问串，问所有子串中的权值最大值。
现在知道了，对于子串问题，如果是给定一个串问对应的所有子串，这样的就不太好用SAM维护，因为SAM上的一个节点，它的所有子串在parent树上没有明显的关系，而更适合用ACAM，在上面跑，每次匹配到的节点到根路径上所有节点都是它的子串，就可以结合个树剖来快速维护这些串的权值信息，所以单点修改，路径查询即可。
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 4e5 + 10;
const int mod = 998244353;
int to[maxn];
struct ACAM {
int c[maxn][26], tot, fail[maxn], val[maxn], ed[maxn];
multiset
queue
int insert(string& str) {
int p = 0;
for (auto ch : str) {
if (!c[p][ch - 'a']) c[p][ch - 'a'] = ++tot;
p = c[p][ch - 'a'];
}
ed[p] = 1;
ms[p].insert(0);
return p;
}
void build() {
for (int i = 0; i < 26; i++)
if (c[0][i])
fail[c[0][i]] = 0, q.push(c[0][i]);
while (!q.empty()) {
int u = q.front(); q.pop();
ed[u] |= ed[fail[u]];
for (int i = 0; i < 26; i++)
if (c[u][i])
fail[c[u][i]] = c[fail[u]][i], q.push(c[u][i]);
else
c[u][i] = c[fail[u]][i];
}
}
} acm;
struct SegmentTree {
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
struct Node {
int mx;
};
Node t[maxn << 2];
SegmentTree() { ; }
void push_up(int rt) { t[rt].mx = max(t[ls].mx, t[rs].mx); }
void modify(int rt, int l, int r, int pos, int acmnode, int preval, int val) {
if (l == r) {
acm.ms[acmnode].erase(acm.ms[acmnode].find(preval));
acm.ms[acmnode].insert(val);
t[rt].mx = *acm.ms[acmnode].rbegin();
return;
}
if (pos <= mid) modify(ls, l, mid, pos, acmnode, preval, val);
else modify(rs, mid + 1, r, pos, acmnode, preval, val);
push_up(rt);
}
int query(int rt, int l, int r, int p, int q) {
if (q < l || p > r) return 0;
if (p <= l && r <= q) return t[rt].mx;
int ans = 0;
return max(query(ls, l, mid, p, q), query(rs, mid + 1, r, p, q));
}
} seg;
struct HLD {
vector
int dep[maxn], fa[maxn], mp[maxn], siz[maxn], n;
int ncnt, son[maxn], top[maxn], L[maxn], R[maxn];
void dfs1(int u, int f, int deep) {
dep[u] = deep, siz[u] = 1, fa[u] = f;
for (auto v : G[u]) {
if (v == f) continue;
dfs1(v, u, deep + 1);
siz[u] += siz[v];
if (son[u] == 0 || siz[son[u]] < siz[v])
son[u] = v;
}
}
void dfs2(int u, int topf) {
L[u] = ++ncnt, top[u] = topf, mp[ncnt] = u;
if (!son[u]) {
R[u] = ncnt;
return;
}
dfs2(son[u], topf);
for (auto v : G[u]) {
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
R[u] = ncnt;
}
int query(int u, int v) {
int res = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]])
swap(u, v);
res = max(res, seg.query(1, 1, n, L[top[u]], L[u]));
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
res = max(res, seg.query(1, 1, n, L[v], L[u]));
return res;
}
} hld;
void solve() {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) {
string str; cin >> str;
to[i] = acm.insert(str);
}
acm.build();
for (int i = 1; i <= acm.tot; i++)
hld.G[acm.fail[i]].push_back(i);
n = acm.tot + 1;
hld.n = n;
hld.dfs1(0, 0, 0);
hld.dfs2(0, 0);
while (m--) {
int op; cin >> op;
if (op == 1) {
int id, val; cin >> id >> val;
seg.modify(1, 1, n, hld.L[to[id]], to[id], acm.val[id], val);
acm.val[id] = val;
} else {
string str; cin >> str;
int ans = 0, flag = 0, p = 0;
for (auto ch : str) {
p = acm.c[p][ch - 'a'];
flag |= acm.ed[p];
ans = max(ans, hld.query(p, 0));
}
if (!flag) cout << -1 << "\n";
else cout << ans << "\n";
}
}
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
CF116D. Mysterious Code
https://codeforces.com/contest/1163/problem/D
题意是给定含字符串str,又给定字符串S，T。要求把str的号替换为小写字母，使得str里s出现次数-T出现次数最大，数据范围比较小。
直接看题解了，不过也确实没有这方面意识，会去考虑ac自动机上dp。dp[i][j]表示当前考虑到str的第 \(i\) 位，匹配到了自动机的节点 \(j\) 时的权值，然后26个字母枚举转移，预处理一下自动机上S 和 T的终止节点的链，然后匹配到的节点就知道对应权值对应变化。是个不错思想，可以加训一下ac自动机上dp。
点击查看代码
#include
#define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 2e3 + 10;
const int mod = 998244353;
struct ACm {
// 信息存在val数组里，这里val存数量
queue
int c[maxn][26], ed[maxn], fail[maxn], cnt;
int tag[maxn];
int insert(string& str) {
int len = str.length(), now = 0;
for (int i = 0; i < len; i++) {
int v = str[i] - 'a';
if (!c[now][v])
c[now][v] = ++cnt;
now = c[now][v];
}
return now;
}
void build() { // 建立fail指针
for (int i = 0; i < 26; i++)
if (c[0][i])
fail[c[0][i]] = 0, q.push(c[0][i]);
while (!q.empty()) {
int u = q.front();
tag[u] += tag[fail[u]];
q.pop();
for (int i = 0; i < 26; i++)
if (c[u][i])
fail[c[u][i]] = c[fail[u]][i], q.push(c[u][i]);
else
c[u][i] = c[fail[u]][i];
}
}
} ac;
int dp[maxn][maxn];
void solve() {
string str, a, b;
cin >> str >> a >> b;
ac.tag[ac.insert(a)] = 1;
ac.tag[ac.insert(b)] = -1;
ac.build();
memset(dp, -0x3f, sizeof dp);
dp[0][0] = 0;
int n = str.length();
for (int i = 0; i < n; i++)
for (int j = 0; j <= ac.cnt; j++) {
for (int k = 0; k < 26; k++) {
if (str[i] - 'a' != k && str[i] != '*') continue;
if (dp[i][j] == dp[0][1]) continue;
int v = ac.c[j][k];
dp[i + 1][v] = max(dp[i + 1][v], dp[i][j] + ac.tag[v]);
}
}
int ans = -inf;
for (int j = 0; j <= ac.cnt; j++)
ans = max(ans, dp[n][j]);
cout << ans << "\n";
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
CF1483F
https://codeforces.com/problemset/problem/1483/F
题意，给 \(n\) 个字符串，求二元组 \((i,j)\)数量，满足一个是另一个的最大子串，也就是不存在第三个串恰好位于中间。考虑用ACAM做多模式串匹配问题，枚举长的串，然后容易预处理每个前缀能匹配到的最长模式串(而且最后一个时要特判，不然就找自身了)，然后关键处理包含关系，再去处理每个前缀对应的最长串的左端点，倒叙枚举判断包含关系。然后把所有可能的串编号记录下来，最后判断的依据是，在串里的出现总次数，等于未被包含的串出现总次数，所以再用个dfn序树状数组，就可以查询这些串在该枚举串的出现总次数，是个很妙的题。
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 998244353;
struct ACm {
queue
int c[maxn][26], lst[maxn], fail[maxn], tot, lth[maxn];
int insert(string& str, int id) {
int len = str.length(), p = 0;
for (int i = 0; i < len; i++) {
int v = str[i] - 'a';
if (!c[p][v])
c[p][v] = ++tot, lth[tot] = lth[p] + 1;
p = c[p][v];
}
lst[p] = id;
return p;
}
void build() { // 建立fail指针
for (int i = 0; i < 26; i++)
if (c[0][i])
fail[c[0][i]] = 0, q.push(c[0][i]);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++)
if (c[u][i])
fail[c[u][i]] = c[fail[u]][i], q.push(c[u][i]);
else
c[u][i] = c[fail[u]][i];
}
}
} ac;
struct BIT {
int len;
vector
int lowbit(int x) {return x & -x;}
BIT (int n) {len = n + 3;t.resize(len);}
void update(int i, int x) {
for (int pos = i; pos < len; pos += lowbit(pos))
t[pos] += x;
}
int query(int i) {
int res = 0;
for (int pos = i; pos; pos -= lowbit(pos))
res += t[pos];
return res;
}
};
string str[maxn];
vector
int ncnt, L[maxn], R[maxn], in[maxn], to[maxn];
void dfs(int u) {
L[u] = ++ncnt;
for (auto v : G[u]) {
if (!ac.lst[v])
ac.lst[v] = ac.lst[u];
dfs(v);
}
R[u] = ncnt;
}
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> str[i];
to[i] = ac.insert(str[i], i);
}
ac.build();
for (int i = 1; i <= ac.tot; i++)
G[ac.fail[i]].push_back(i);
dfs(0);
BIT bit(ncnt + 3);
ll ans = 0;
for (int i = 1; i <= n; i++) {
int p = 0;
vector
for (int j = 0; j < str[i].length(); j++) {
char ch = str[i][j];
p = ac.c[p][ch - 'a'];
bit.update(L[p], 1);
tem.push_back(p);
}
int mnpos = inf;
for (int j = (int)str[i].length() - 1; j >= 0; j--) {
int u = tem[j];
if (j == (int)str[i].length() - 1) u = ac.fail[u];
if (ac.lst[u] && j + 1 - ac.lth[to[ac.lst[u]]] + 1 < mnpos) {
mnpos = j + 1 - ac.lth[to[ac.lst[u]]] + 1;
in[ac.lst[u]]++;
if (in[ac.lst[u]] == 1) vec.push_back(ac.lst[u]);
}
}
for (auto it : vec) {
int debug = bit.query(R[to[it]]) - bit.query(L[to[it]] - 1);
if (in[it] == bit.query(R[to[it]]) - bit.query(L[to[it]] - 1))
ans++;
in[it] = 0;
}
for (auto it : tem) bit.update(L[it], -1);
}
cout << ans << "\n";
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
洛谷P3449
https://www.luogu.com.cn/problem/P3449
直接记结论:两个回文串拼起来还是回文串，必须要最短循环节相同，而且这里循环节得整除字符串长度，不能简单的 \(n-border[n]\)，不整除时特判一下。
洛谷P4287 双倍回文
https://www.luogu.com.cn/problem/P4287
题意就是求给定字符串的最长双倍回文串，双倍回文串就是两个完全相同的偶回文串拼接起来的大回文串。
之前做过马拉车做法，学过PAM后回来补一下PAM做法。题解区有一种均摊维护trans指针的做法没太懂，我只会fail树倍增跳到祖先节点里面恰好长度小等于一半的，看长度是不是恰好等于大回文串的一半，因为fail树上定义是回文后缀，又恰好长度一半，那就说明肯定符合条件是双倍回文串，\(nlogn\) 不用脑子写法。而且现在我改了倍增数组的二维，因为缓存命中问题可以大大减少常数。
洛谷P6216 回文匹配
题意大概就是给两个串S和T，问S的奇回文串里T的出现总次数。
首先回文问题无脑建出PAM，就可以知道所有本质不同的奇回文串的长度、出现次数，现在只要再维护出每种本质不同的回文串里T的出现次数。暴力的方法是直接kmp，然后会发现由于这些回文串都是S的子串，所以可以只对S串一遍kmp，维护所有匹配到的位置求前缀和(也就是endpos处+1，前缀和)，然后只要知道回文串的起始位置，就可以 \(O(1)\) 求该回文串里T的出现次数。然后起始位置就可以在建PAM过程中随便维护一个endpos和len就可以得到。
cf587F Duff is Mad
https://codeforces.com/problemset/problem/587/F
拖了很久的ACAM经典根号分治题，在对ACAM的FAIL树比较理解之后再做这个会好做很多。
题意是给 \(N\) 个字符串，多次询问，每次询问区间[l,r]内的字符串在第 \(k\) 个字符串里的出现次数。
首先很容易想到差分，然后注意到题目里是给定 \(n\) 个串的总串长有限制，而对询问里的 \(k\) 的串长和没有限制。然后ACAM的字符串匹配问题，其实就是FAIL树的子树问题，要么是对文本串的子树里面求和，要么是询问串节点链求和，都是用DFN序加BIT可以做的，记住核心就是，用字符串在ACAM上跑，每跑到一个节点，表示该节点到根的fail链上所有节点都匹配上了。
这题对询问的 \(k\) 的串长根号分治，如果串很长，那么这样的串不超根号个，所以每个串都可以对所有 \(n\) 个字符串遍历一下来求得到前缀和数组，对该串的询问就可以差分一下得到。那么如何得到该前缀和数组，等价于 \(sum[i]\) 表示 \(1 - i\) 的字符串在 \(k\) 串里的出现次数总和，等价于让 \(k\) 串在ACAM里面跑，每个节点到根的链上， \(1-i\)的endpos被覆盖到的次数。也就是记录 \(1-i\) 每个串的结尾对应ACAM节点，对子树求和，然后对 \(k\) 串的每个节点单点加一。这样的复杂度是 \(len[k]log + nlogn\)。
对于短的串，肯定要让询问根短的串长挂钩，就可以把短串的询问挂在对应的l-1和r位置，遍历 \(n\) 个串，每次把endpos的子树+1，然后遍历对应询问的短串，看看每个节点被覆盖了多少次求和。
一开始没看懂为什么需要根号分治，后来发现关键在于这两种离线的挂法不一样，短串的询问方式是把询问挂在差分的地方，长串的离线是把询问挂在询问串上，所以这样复杂度才是正确的。总算是补完了这个题，现在ACAM还差二进制分组那个一直懒得写了。不知道什么时候会补那个题。
点击查看代码
#include
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair
#define tii tuple
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
struct ACAM {
// 信息存在val数组里，这里val存数量
queue
int c[maxn][26], ed[maxn], fail[maxn], tot;
int insert(string& str) {
int len = str.length(), p = 0;
for (int i = 0; i < len; i++) {
int v = str[i] - 'a';
if (!c[p][v])
c[p][v] = ++tot;
p = c[p][v];
}
return p;
}
void build() { // 建立fail指针
for (int i = 0; i < 26; i++)
if (c[0][i])
fail[c[0][i]] = 0, q.push(c[0][i]);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++)
if (c[u][i])
fail[c[u][i]] = c[fail[u]][i], q.push(c[u][i]);
else
c[u][i] = c[fail[u]][i];
}
}
} ac;
struct BIT {
int len;
vector
BIT (int n) {len = n + 5;t.resize(len);}
int lowbit(int x) {return x & -x;}
void update(int i, int x) {
for (int pos = i; pos < len; pos += lowbit(pos))
t[pos] += x;
}
ll query(int i) {
ll res = 0;
for (int pos = i; pos; pos -= lowbit(pos))
res += t[pos];
return res;
}
};
string str[maxn];
vector
vector
int L[maxn], R[maxn], ncnt, tag[maxn], to[maxn];
ll ans[maxn], temans[maxn];
void dfs(int u) {
L[u] = ++ncnt;
for (auto v : G[u])
dfs(v);
R[u] = ncnt;
}
void solve() {
int n, q; cin >> n >> q;
int sq = 350;
for (int i = 1; i <= n; i++) {
cin >> str[i];
to[i] = ac.insert(str[i]);
if ((int)str[i].length() > sq)
tag[i] = 1;
}
ac.build();
for (int i = 1; i <= ac.tot; i++)
G[ac.fail[i]].push_back(i);
dfs(0);
for (int i = 1; i <= q; i++) {
int l, r, k; cin >> l >> r >> k;
if (tag[k]) {
query1[k].push_back(tii(l - 1, -1, i));
query1[k].push_back(tii(r, 1, i));
}
else {
query2[l - 1].push_back(tii(k, -1, i));
query2[r].push_back(tii(k, 1, i));
}
}
{
//处理长串
for (int i = 1; i <= n; i++) {
if (tag[i] && !query1[i].empty()) {
BIT bit(ncnt + 1);
int p = 0;
for (auto ch : str[i]) {
p = ac.c[p][ch - 'a'];
bit.update(L[p], 1);
}
for (int j = 1; j <= n; j++) {
temans[j] = temans[j - 1];
temans[j] += bit.query(R[to[j]]) - bit.query(L[to[j]] - 1);
}
for (auto [pos, sgn, id] : query1[i]) {
ans[id] += sgn * temans[pos];
}
}
}
}
{
//处理短串
BIT bit(ncnt + 1);
for (int i = 1; i <= n; i++) {
bit.update(L[to[i]], 1);
bit.update(R[to[i]] + 1, -1);
for (auto [k, sgn, id] : query2[i]) {
ll sum = 0, p = 0;
for (auto ch : str[k]) {
p = ac.c[p][ch - 'a'];
sum += bit.query(L[p]);
}
ans[id] += sgn * sum;
}
}
}
for (int i = 1; i <= q; i++)
cout << ans[i] << "\n";
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}