CONTENT: 字符串 I
DETAIL: 后缀数组、字典树
BB
争取零点前发出去
这次review后缀数组的时候，发现全忘了，不过也进一步理解了一波？
蒟蒻还是太菜了QAQ
Introduction
本次内容包含了2道后缀数组可解与1道字典树可解的题目
Tandem - CodeChef TANDEM
Description
给定字符串，找出其中形如AAA的子串的数量，并将其分为两类，第一类是AAA后的第一个字符与A的第一个字符相同的子串，第二类是不相同的子串。样例解释如下：
In summary, s[1..12], s[2..13], s[3..14], s[3..5], s[7..9], s[11..13], s[14..16], s[15..17] are all tandem substrings. Out of which, s[3..14], s[3..5], s[7..9], s[11..13], s[15..17] are all interesting tandems. Rest tandem substrings, s[1..12], s[2..13], s[14..16] are all boring tandems.
Sample Input
abaaabaaabaaabbbb
Sample Output
5 3
Solution - 后缀数组
基本结论：枚举A的长度L，那么AAA必然需要经过位置0, L, 2L, …其中恰好三个。这个画画图就可知
那么先枚举L，再连续三个枚举，求出他们的最长公共后缀lcs，与最长公共前缀lcp，记all=min(lcs,L)+min(lcp, L)-1，其中min是因为不能越过别的点（距离为L），分以下三种情况：
① all < L，那么是无解的。因为公共部分不足L
② all >= L 且 lcp <= L，那么对第一类串的总数贡献为all-L，第二类串的贡献为1。首先，画图可知前一部分的结论，后面的1是当整个串覆盖住一整个lcp时，后面那个字符肯定是不一样的，如果一样的话会被记入lcp，画一下图就知道啦
③ all >= L 且 lcp > L，那么对第一类串的总数贡献为all-L+1，第二类串的贡献为0。这里的0是因为lcp超过L，撑死了就把整个串的左端点放在kL的位置，这样是不足以覆盖整个lcp的，所以下一个字符肯定是首字符
最后求解lcs和lcp用RMQ+后缀数组
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)200000 + 15;
char s1[N], s2[N];
struct SuffixArray {
int t1[N], t2[N], sa[N], rk[N], height[N][19], buc[N];
inline void buildSA(char* s, int n) {
int m = 200;
int* x = t1, *y = t2;
memset(buc + 1, 0, sizeof(int) * m);
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, sizeof(int) * m);
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 i, int j, int k) {
int st = min(rk[i], min(rk[j], rk[k])) + 1;
int ed = max(rk[i], max(rk[j], rk[k]));
int bck = floor(log2(ed - st + 1));
return min(height[st][bck], height[ed - (1 << bck) + 1][bck]);
}
};
SuffixArray SA1, SA2;
int main() {
while(~scanf("%s", s1 + 1)) {
int n = strlen(s1 + 1);
memcpy(s2 + 1, s1 + 1, n * sizeof(char));
reverse(s2 + 1, s2 + 1 + n);
SA1.buildSA(s1, n);
SA1.getHeight(s1, n);
SA1.buildRMQ(n);
SA2.buildSA(s2, n);
SA2.getHeight(s2, n);
SA2.buildRMQ(n);
ll ans1 = 0, ans2 = 0;
for(int len = 1; 1 + 2 * len <= n; len++) {
for(int i = 1; i + 2 * len <= n; i += len) {
int j = i + len, k = i + 2 * len;
int lcp = SA1.query(i, j, k);
int lcs = SA2.query(n - i + 1, n - j + 1, n - k + 1);
ll all = min(lcp, len) + min(lcs, len) - 1;
if(all >= len) {
if(lcp <= len) {
ans1 += (all - len);
ans2++;
} else {
ans1 += (all - len + 1);
}
}
}
}
printf("%lld %lld\n", ans2, ans1);
}
}
summary
- 枚举A的长度L，那么AAA必然需要经过位置0, L, 2L, …其中恰好三个。这个方法貌似是个非常套路的方法，从下题中也可知，稍微想想可知这种方法能够实现不重复枚举
Maximum repetition substring - POJ 3693
Description
给定一个串，找出一个子串，使得可以其最小循环节构成其的次数是所有子串中最多的，如果有多个串，那么输出字典序最小的
Sample Input
ccabababc
daabbccaa
#
Sample Output
Case 1: ababab
Case 2: aa
Solution - 后缀数组
和上题类似，仍然采用枚举L+固定点的方法
当枚举的长度为L时，长度大于1的串肯定经过0, L, 2L, …，中的至少连续两个，lcp(s + i, s + i + L) + lcs(s + i, s + i + L) - 1为长度为L的循环节能够不完全组成的最大长度，这个画图可知，有点像kmp算法求循环节（？可能）
实践证明，如果单纯采用上题的方法，会得到一个TLE，（而且好像还不太对） QAQ
回到lcp(s + i, s + i + L)，这个时候要求lcs是因为前面可能还有，那么可以考虑把两个点往前挪一挪再求lcp，而前面的额外贡献最多就是1。要往前挪多少呢？只需要往前挪L-lcp%L，这样刚好补全了lcp末尾不够L的部分。为什么只需要往前挪L-lcp%L？首先挪这个长度后算次数如果比原来多，那么也就多1，再往前挪前面又不够L，不会有更多贡献。其次如果算出来比原来少，那么再往前挪也不会增加，因为这个部分依然需要经过的。因此直接把两个点左挪L-lcp%L，再求lcp，取最大值，最后经过这两个点中的串次数最大值为lcp/L+1
上面枚举完成，最后字典序最小的部分，利用sa数组本身是字典序顺序，枚举完成。然而这部分复杂度高达O(n^2)，但是能过？？？
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = (int)100000 + 15;
char s1[N];
char s[N];
int que[N], qcnt;
struct SuffixArray {
int t1[N], t2[N], sa[N], rk[N], height[N][19], buc[N];
inline void buildSA(char* s, int n) {
int m = 27;
int* x = t1, *y = t2;
memset(buc + 1, 0, sizeof(int) * m);
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, sizeof(int) * m);
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 i, int j) {
int st = min(rk[i], rk[j]) + 1;
int ed = max(rk[i], rk[j]);
int bck = floor(log2(ed - st + 1));
return min(height[st][bck], height[ed - (1 << bck) + 1][bck]);
}
};
SuffixArray SA1;
int main() {
int csn = 1;
while(~scanf("%s", s + 1) && s[1] != '#') {
int n = strlen(s + 1);
for(int i = 1; i <= n; i++) {
s1[i] = s[i] - 'a' + 1;
}
SA1.buildSA(s1, n);
SA1.getHeight(s1, n);
SA1.buildRMQ(n);
int maxx = 0;
qcnt = 0;
for(int len = 1; 1 + len <= n; len++) {
for(int i = 1; i + len <= n; i += len) {
int j = i + len;
int lcp = SA1.query(i, j);
int tmp = lcp / len + 1;
if(lcp % len) {
int delta = len - lcp % len;
if(i - delta < 0 || j - delta < 0) {
continue;
}
tmp = max(tmp, SA1.query(i - delta, j - delta) / len + 1);
}
if(tmp > maxx) {
maxx = tmp;
qcnt = 0;
que[qcnt++] = len;
} else if(tmp == maxx){
que[qcnt++] = len;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < qcnt; j++) {
int st = SA1.sa[i];
int ed = SA1.sa[i] + que[j];
if(ed > n) {
continue;
}
if(SA1.query(st, ed) >= (maxx - 1) * que[j]) {
printf("Case %d: %.*s\n", csn++, que[j] * maxx, s + st);
goto ctnLoop;
}
}
}
ctnLoop:
continue;
}
}
summary
- 对于一个串s，将其偏移L后做lcp，能够得到一个不完全由偏移这一段为循环节构成的串
Repository - HDU 2846
Description
给定N个串，Q个询问，每个询问给出一个串，问这个串在多少串中作为子串出现
串的长度均不大于20
Sample Input
20
ad
ae
af
ag
ah
ai
aj
ak
al
ads
add
ade
adf
adg
adh
adi
adj
adk
adl
aes
5
b
a
d
ad
s
Sample Output
0
20
11
11
2
Solution - 字典树
遗留题目 QAQ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)10000 * 220 + 15;
char s[N];
int ch[N][26];
int cnt[N], pre[N];
int tot;
inline void init() {
memset(ch[1], 0, sizeof(ch[1]));
pre[1] = cnt[1] = 0;
tot = 1;
}
inline void newNode(int& x) {
x = ++tot;
pre[x] = cnt[x] = 0;
memset(ch[x], 0, sizeof(ch[x]));
}
inline void push(char* s, int j) {
int p = 1;
for(int i = 0; s[i]; i++) {
int idx = s[i] - 'a';
if(!ch[p][idx]) {
newNode(ch[p][idx]);
}
p = ch[p][idx];
if(pre[p] != j) {
pre[p] = j;
cnt[p]++;
}
}
}
inline int query(char* s) {
int p = 1;
for(int i = 0; s[i]; i++) {
int idx = s[i] - 'a';
if(!ch[p][idx]) {
return 0;
}
p = ch[p][idx];
}
return cnt[p];
}
int main() {
init();
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%s", s);
for(int j = 0; s[j]; j++) {
push(s + j, i);
}
}
int m;
scanf("%d", &m);
while(m--) {
scanf("%s", s);
printf("%d\n", query(s));
}
}
