CONTENT: 字符串 II
DETAIL: 后缀数组、后缀自动机、广义后缀自动机
BB
因为课程关系所以顺便回顾了一下ISAP算法，然后发现网上很多解释不太对，所以写了这篇文
（蒟蒻还是太菜了 QAQ）
Introduction
由幼儿园知识可知（划掉），网络流中求最大流的方法有Ford-Fulkerson算法，其时间复杂度是O(f*m)
后缀自动机二·重复旋律5 - HihoCoder 1445
Description
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。
现在小Hi想知道一部作品中出现了多少不同的旋律？
Sample Input
aab
Sample Output
5
Solution - SAM
本题即求字符串中不同子串的数量，可用SA求，也可用SAM求
在刷题记系列的《后缀自动机》中，本题使用了SAM的parent树性质求，即每一个节点表示的长度为[len(fa(x)) + 1, len(x)]
这次利用DAG图性质，使用DP求解，定义DP状态dp(st)为在状态st下以这一状态代表的字符串开头的不同字符串的数量，则dp(st) = 1 + sum(dp(nxt_st))
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000000;
const int SIZE = 26;
char s[N];
ll dp[N << 1];
struct SuffixAutomaton {
int slink[N << 1], len[N << 1], trans[N << 1][SIZE];
int lst, tot;
inline void init() {
tot = 0;
lst = newNode();
slink[lst] = len[lst] = 0;
}
inline int newNode() {
int x = ++tot;
memset(trans[x], 0, sizeof(trans[x]));
dp[x] = 0;
return x;
}
inline void push(int val) {
int p = lst, np = newNode();
len[np] = len[p] + 1;
for(; p && trans[p][val] == 0; p = slink[p]) {
trans[p][val] = np;
}
if(p == 0) {
slink[np] = 1;
} else {
int q = trans[p][val];
if(len[q] == len[p] + 1) {
slink[np] = q;
} else {
int nq = ++tot;
slink[nq] = slink[q];
len[nq] = len[p] + 1;
memcpy(trans[nq], trans[q], sizeof(trans[q]));
slink[np] = slink[q] = nq;
for(; p && trans[p][val] == q; p = slink[p]) {
trans[p][val] = nq;
}
}
}
lst = np;
}
};
SuffixAutomaton sam;
ll solve(int u) {
if(dp[u]) {
return dp[u];
}
dp[u] = 1;
for(int val = 0; val < SIZE; val++) {
if(sam.trans[u][val]) {
dp[u] += solve(sam.trans[u][val]);
}
}
return dp[u];
}
int main() {
while(~scanf("%s", s)) {
//memset(dp, 0, sizeof(dp));
sam.init();
for(int i = 0; s[i]; i++) {
sam.push(s[i] - 'a');
}
printf("%lld\n", solve(1) - 1);
}
}
Substrings and Repetitions - CodeChef ANUSAR
Description
给定一个字符串S和若干询问Fi。对于每个询问，输出S中出现至少Fi次的子串的个数（可相同）。
1 <= |S| <= 2*10^5, 2 <= Q <= 2*10^5
Sample Input
1
aaeddf
4
1
2
3
4
Sample Output
21
4
0
0
Solution - SAM
利用parent树性质求出|endpos|，那么每个状态中含有len(x) - len(fa(x))个子串，至少出现|endpos|次
所以预处理一波，求ans[|endpos|]，然后前缀和，对询问离线回答就ok
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200000 + 15;
const int SIZE = 26;
char s[N];
ll ans[N];
static queue<int> que;
struct SuffixAutomaton {
int slink[N << 1], len[N << 1], trans[N << 1][SIZE], cnt[N << 1], buc[N << 1], vec[N << 1], idg[N << 1];
ll dp[N << 1];
int lst, tot;
inline void init() {
tot = 0;
lst = newNode();
slink[lst] = len[lst] = 0;
}
inline int newNode() {
int x = ++tot;
memset(trans[x], 0, sizeof(trans[x]));
dp[x] = idg[x] = cnt[x] = 0;
return x;
}
inline void push(int val) {
int p = lst, np = newNode();
len[np] = len[p] + 1;
cnt[np] = 1;
for(; p && trans[p][val] == 0; p = slink[p]) {
trans[p][val] = np;
}
if(p == 0) {
slink[np] = 1;
} else {
int q = trans[p][val];
if(len[q] == len[p] + 1) {
slink[np] = q;
} else {
int nq = ++tot;
cnt[nq] = dp[nq] = 0;
slink[nq] = slink[q];
len[nq] = len[p] + 1;
memcpy(trans[nq], trans[q], sizeof(trans[q]));
slink[np] = slink[q] = nq;
for(; p && trans[p][val] == q; p = slink[p]) {
trans[p][val] = nq;
}
}
}
lst = np;
}
inline void getCnt() {
memset(buc, 0, (tot + 1) * sizeof(int));
for(int i = 2; i <= tot; i++) {
buc[len[i]]++;
}
for(int i = 2; i <= tot; i++) {
buc[i] += buc[i - 1];
}
for(int i = tot; i >= 2; i--) {
vec[buc[len[i]]--] = i;
}
for(int i = tot - 1; i >= 1; i--) {
int u = vec[i];
cnt[slink[u]] += cnt[u];
}
cnt[1] = 0;
}
inline void solve() {
getCnt();
for(int i = 1; i <= tot; i++) {
for(int j = 0; j < SIZE; j++) {
if(trans[i][j]) {
idg[trans[i][j]]++;
}
}
}
dp[1] = 1;
que.push(1);
while(!que.empty()) {
int u = que.front();
que.pop();
ans[cnt[u]] += dp[u] * cnt[u];
for(int j = 0; j < SIZE; j++) {
int v = trans[u][j];
if(v) {
dp[v] += dp[u];
if((--idg[v]) == 0) {
que.push(v);
}
}
}
}
}
};
SuffixAutomaton sam;
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n = 0;
scanf("%s", s);
sam.init();
for(int i = 0; s[i]; i++) {
sam.push(s[i] - 'a');
n++;
}
memset(ans, 0, (n + 3) * sizeof(ll));
sam.solve();
for(int i = n - 1; i > 0; i--) {
ans[i] += ans[i + 1];
}
int q;
scanf("%d", &q);
while(q--) {
int f;
scanf("%d", &f);
printf("%lld\n", ans[f]);
}
}
}
Martian Strings - CodeForces 149E
Description
给定一个串，在给定M个串，问这M个串中有多少个串能切成两半，使得这两半都能在一个串中不重叠且顺序出现
Sample Input
ABCBABA
2
BAAB
ABBA
Sample Output
1
Solution - SAM
本题理论上可以用AC自动机做，按CF神机的速度的话 （大雾
对原串跑LCP和LCS，对每一个LCP维护出现的最小位置，即SAM中第一次出现的位置；对每一个LCS维护出现的最大位置，而LCS由原串倒置后建立，故仍然是SAM中第一次出现的位置
最后对每一个串，枚举切割位置，只要位置存在且不重叠就是ok的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 15;
const int SIZE = 26;
char s[N];
static queue<int> que;
struct SuffixAutomaton {
int slink[N << 1], len[N << 1], trans[N << 1][SIZE], pos[N];
ll dp[N << 1];
int lst, tot;
inline void init() {
tot = 0;
lst = newNode();
slink[lst] = len[lst] = 0;
}
inline int newNode() {
int x = ++tot;
memset(trans[x], 0, sizeof(trans[x]));
return x;
}
inline void push(int val, int idx) {
int p = lst, np = newNode();
pos[np] = idx;
len[np] = len[p] + 1;
for(; p && trans[p][val] == 0; p = slink[p]) {
trans[p][val] = np;
}
if(p == 0) {
slink[np] = 1;
} else {
int q = trans[p][val];
if(len[q] == len[p] + 1) {
slink[np] = q;
} else {
int nq = ++tot;
slink[nq] = slink[q];
pos[nq] = pos[q];
len[nq] = len[p] + 1;
memcpy(trans[nq], trans[q], sizeof(trans[q]));
slink[np] = slink[q] = nq;
for(; p && trans[p][val] == q; p = slink[p]) {
trans[p][val] = nq;
}
}
}
lst = np;
}
};
SuffixAutomaton sam1, sam2;
int prefPos[N], suffPos[N];
inline bool query(char* s, int n) {
memset(prefPos, -1, n * sizeof(int));
memset(suffPos, -1, n * sizeof(int));
for(int i = 0, p = 1; i < n; i++) {
int j = s[i] - 'A';
if(sam1.trans[p][j]) {
p = sam1.trans[p][j];
prefPos[i] = sam1.pos[p];
} else {
break;
}
}
for(int i = n - 1, p = 1; i >= 0; i--) {
int j = s[i] - 'A';
if(sam2.trans[p][j]) {
p = sam2.trans[p][j];
suffPos[i] = sam2.pos[p];
} else {
break;
}
}
for(int i = 0; i + 1 < n; i++) {
if(prefPos[i] == -1 || suffPos[i + 1] == -1) {
continue;
}
if(prefPos[i] < suffPos[i + 1] ) {
return true;
}
}
return false;
}
int main() {
while(~scanf("%s", s)) {
sam1.init();
sam2.init();
int n = strlen(s);
for(int i = 0; i < n; i++) {
sam1.push(s[i] - 'A', i);
}
for(int i = n - 1; i > 0; i--) {
sam2.push(s[i] - 'A', i);
}
int m, sum = 0;
scanf("%d", &m);
while(m--) {
scanf("%s", s);
int res = query(s, strlen(s));
//printf("res = %d\n", res);
sum += res;
}
printf("%d\n", sum);
}
}
Little Elephant and Strings - CodeForces 204E
Description
给定N个串，求每一个串中的每一个子串作为子串出现在这N个串中至少k个串的个数
Sample Input
3 1
abc
a
ab
7 4
rubik
furik
abab
baba
aaabbbababa
abababababa
zero
Sample Output
6 1 3
1 0 9 9 21 30 0
Solution 1 - 后缀数组
枚举每一个串中的每一个后缀，对于每一个后缀，二分最大长度，使用RMQ求出这一长度下能够扩展的位置，位置差即对应不同后缀的个数，这些个数能够覆盖k个原串，则ok，则计算出最大长度后累加
最后最关键的问题是如果能够知道覆盖k个原串？可以使用尺取法，对每一个排名位置预处理出能够到达k个原串的位置，然后判断的时候判断能否超过位置就完事
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)200000 + 15;
const int BASE = 19;
char s[N], tmpStr[N];
int t1[N], t2[N], buc[N], sa[N], height[N][BASE], rk[N];
int kpos[N], cnt[N], belong[N], edpos[N];
ll ans[N];
inline void buildSA(char* s, int n, int m = 128) {
int* x = t1, * y = t2;
memset(buc + 1, 0, m * sizeof(int));
for(int i = 1; i <= n; i++) {
buc[x[i] = s[i]]++;
}
for(int i = 2; i <= m; i++) {
buc[i] += buc[i - 1];
}
for(int i = n; i >= 1; i--) {
sa[buc[x[i]]--] = i;
}
for(int k = 1; k <= n; k <<= 1) {
int p = 0;
for(int i = n; i > n - k; i--) {
y[++p] = i;
}
for(int i = 1; i <= n; i++) {
if(sa[i] > k) {
y[++p] = sa[i] - k;
}
}
memset(buc + 1, 0, m * sizeof(int));
for(int i = 1; i <= n; i++) {
buc[x[i]]++;
}
for(int i = 2; i <= m; i++) {
buc[i] += buc[i - 1];
}
for(int i = n; i >= 1; i--) {
sa[buc[x[y[i]]]--] = y[i];
}
swap(x, y);
p = x[sa[1]] = 1;
for(int i = 2; i <= n; i++) {
int a = sa[i] + k > n ? -1 : y[sa[i] + k];
int b = sa[i - 1] + k > n ? -1 : y[sa[i - 1] + k];
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && a == b) ? p : ++p;
}
if(p >= n) {
break;
}
m = p;
}
}
inline void getHeight(char* s, int n) {
for(int i = 1; i <= n; i++) {
rk[sa[i]] = i;
}
int k = 0;
for(int i = 1; i <= n; i++) {
if(rk[i] == 1) {
continue;
}
if(k) {
k--;
}
int j = sa[rk[i] - 1];
while(s[i + k] == s[j + k]) {
k++;
}
height[rk[i]][0] = k;
}
}
inline void buildRMQ(int n) {
for(int j = 1; (1 << j) <= n; j++) {
for(int i = 1; i + (1 << j) - 1 <= n; i++) {
height[i][j] = min(height[i][j - 1], height[i + (1 << (j - 1))][j - 1]);
}
}
}
inline int query(int l, int r) {
int j = (int)floor(log2(r - l + 1));
return min(height[l][j], height[r - (1 << j) + 1][j]);
}
inline void buildKPos(int n, int k) {
int r = 0, res = 0;
for(int i = 1; i <= n; i++) {
if(i > 1 && (--cnt[belong[sa[i - 1]]]) == 0 && res > 0) {
res--;
}
while(res < k && r <= n) {
cnt[belong[sa[++r]]]++;
if(cnt[belong[sa[r]]] == 1) {
res++;
if(res == k) {
break;
}
}
}
if(r > n) {
return;
}
kpos[i] = r;
}
}
inline bool check(int x, int len, int n) {
int ansl = rk[x];
if(height[rk[x]][0] >= len) {
int l = 1, r = rk[x] - 1;
while(l <= r) {
int m = (l + r) >> 1;
if(query(m + 1, rk[x]) >= len) {
r = m - 1;
ansl = m;
if(kpos[ansl] && (kpos[ansl] <= rk[x] || query(ansl + 1, kpos[ansl]) >= len)) {
return true;
}
} else {
l = m + 1;
}
}
}
return kpos[ansl] && (kpos[ansl] <= rk[x] || query(ansl + 1, kpos[ansl]) >= len);
}
int main() {
int m, k;
int n = 0;
scanf("%d%d", &m, &k);
for(int i = 1; i <= m; i++) {
scanf("%s", tmpStr);
for(int j = 0; tmpStr[j]; j++) {
s[++n] = tmpStr[j] - 'a' + 2;
belong[n] = i;
}
edpos[i] = n;
s[++n] = 1;
}
s[n--] = 0;
buildSA(s, n, 30);
getHeight(s, n);
buildRMQ(n);
buildKPos(n, k);
for(int i = m; i <= n; i++) {
int endPos = edpos[belong[sa[i]]];
int llen = 1, rlen = endPos - sa[i] + 1, anslen = 0;
while(llen <= rlen) {
int mlen = (llen + rlen) >> 1;
if(sa[i] + mlen - 1 > endPos || !check(sa[i], mlen, n)) {
rlen = mlen - 1;
} else {
llen = mlen + 1;
anslen = mlen;
}
}
ans[belong[sa[i]]] += anslen;
}
for(int i = 1; i <= m; i++) {
printf("%lld ", ans[i]);
}
puts("");
}
Solution 2 - 广义SAM
广义SAM后，传递set
（其实复杂度不太对
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200000 + 15;
const int SIZE = 26;
char s[N];
string inStr[N];
ll ans[N];
static queue<int> que;
struct SuffixAutomaton {
unordered_set<int> cnt[N << 1];
int slink[N << 1], len[N << 1], trans[N << 1][SIZE], buc[N << 1], nodeLen[N << 1];
int vec[N << 1];
int lst, tot;
inline void init() {
tot = 0;
lst = newNode();
slink[lst] = len[lst] = 0;
}
inline int newNode() {
int x = ++tot;
memset(trans[x], 0, sizeof(trans[x]));
cnt[x].clear();
return x;
}
inline void push(int val) {
int p = lst, np = newNode();
len[np] = len[p] + 1;
for(; p && trans[p][val] == 0; p = slink[p]) {
trans[p][val] = np;
}
if(p == 0) {
slink[np] = 1;
} else {
int q = trans[p][val];
if(len[q] == len[p] + 1) {
slink[np] = q;
} else {
int nq = ++tot;
cnt[nq] = cnt[q];
slink[nq] = slink[q];
len[nq] = len[p] + 1;
memcpy(trans[nq], trans[q], sizeof(trans[q]));
slink[np] = slink[q] = nq;
for(; p && trans[p][val] == q; p = slink[p]) {
trans[p][val] = nq;
}
}
}
lst = np;
}
inline int dfs(int u, int k) {
if(nodeLen[u] != -1) {
return nodeLen[u];
}
return nodeLen[u] = (cnt[u].size() >= k ? len[u] : dfs(slink[u], k));
}
inline void getCnt(int m, int k) {
for(int i = 2; i <= tot; i++) {
buc[len[i]]++;
}
for(int i = 2; i <= tot; i++) {
buc[i] += buc[i - 1];
}
for(int i = tot; i >= 2; i--) {
vec[buc[len[i]]--] = i;
}
for(int i = 1; i <= m; i++) {
int p = 1;
for(char ch : inStr[i]) {
p = trans[p][ch - 'a'];
cnt[p].emplace(i);
}
}
for(int i = tot - 1; i >= 1; i--) {
int x = vec[i];
for(int ele : cnt[x]) {
cnt[slink[x]].emplace(ele);
}
}
}
inline void getNodeCnt(int k) {
memset(nodeLen, -1, (tot + 1) * sizeof(int));
nodeLen[1] = 0;
for(int i = 2; i <= tot; i++) {
dfs(i, k);
}
}
};
SuffixAutomaton sam;
int main() {
sam.init();
int m, k;
scanf("%d%d", &m, &k);
for(int i = 1; i <= m; i++) {
sam.lst = 1;
scanf("%s", s);
inStr[i] = string(s);
for(int j = 0; s[j]; j++) {
sam.push(s[j] - 'a');
}
}
sam.getCnt(m, k);
sam.getNodeCnt(k);
for(int i = 1; i <= m; i++) {
int p = 1;
for(char ch : inStr[i]) {
p = sam.trans[p][ch - 'a'];
ans[i] += sam.nodeLen[p];
}
}
for(int i = 1; i <= m; i++) {
printf("%lld ", ans[i]);
}
}
