题目1 BZOJ 3676 APIO2014 回文串
算法讨论：
cnt表示回文自动机上每个结点回文串出现的次数。这是回文自动机的定义考查题。
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std; const int C = ;
const int N = + ;
typedef long long ll; char str[N];
int len;
ll ans; struct State {
int len, num, cnt, s, fail, next[C];
}st[N]; struct PTree {
int n, sz, last; int newnode(int len) {
st[sz].len = len;
return sz ++;
} void Init() {
n = sz = last = ;
newnode(); newnode(-);
st[n].s = -;
st[].fail = ;
} int getfail(int x) {
while(st[n - st[x].len - ].s != st[n].s) x = st[x].fail;
return x;
} void count() {
for(int i = sz - ; i >= ; -- i)
st[st[i].fail].cnt += st[i].cnt;
} void add(int c) {
st[++ n].s = c;
int cur = getfail(last);
if(!st[cur].next[c]) {
int now = newnode(st[cur].len + );
st[now].fail = st[getfail(st[cur].fail)].next[c];
st[cur].next[c] = now;
st[now].num = st[st[now].fail].num + ;
}
last = st[cur].next[c];
st[last].cnt ++;
}
}ptree; int main() {
scanf("%s", str);
len = strlen(str);
ptree.Init();
for(int i = ; i < len; ++ i)
ptree.add(str[i] - 'a');
ptree.count();
for(int i = ; i < ptree.sz; ++ i) {
ans = max(ans, 1LL * st[i].cnt * st[i].len);
}
printf("%lld\n", ans);
return ;
}
3676
题目2 BZOJ2565 最长双回文串
算法讨论：
我们考虑计算出每个位置分别作为左右端点时最长回文串的长度。这样答案就是Max{r[i] + l[i + 1]}
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib> using namespace std;
const int C = ;
const int N = + ; struct State {
int len, cnt, num, s, fail, next[C];
void clear() {
len = cnt = num = s = fail = ;
memset(next, , sizeof next);
}
}st[N]; int len, r[N], l[N], ans;
char str[N]; struct Ptree {
int n, sz, last; int newnode(int len) {
st[sz].len = len;
return sz ++;
} void clear() {
for(int i = ; i <= n; ++ i)
st[i].clear();
}
void Init() {
n = sz = last = ;
newnode(); newnode(-);
st[n].s = -;
st[].fail = ;
} int getfail(int x) {
while(st[n - st[x].len - ].s != st[n].s) x = st[x].fail;
return x;
} void count() {
for(int i = sz - ; i >= ; -- i)
st[st[i].fail].cnt += st[i].cnt;
} void add(int c) {
st[++ n].s = c;
int cur = getfail(last);
if(!st[cur].next[c]) {
int now = newnode(st[cur].len + );
st[now].fail = st[getfail(st[cur].fail)].next[c];
st[cur].next[c] = now;
st[now].num = st[st[now].fail].num + ;
}
last = st[cur].next[c];
st[last].cnt ++;
}
}pt; int main() {
scanf("%s", str);
len = strlen(str);
pt.Init();
for(int i = ; i < len; ++ i) {
pt.add(str[i] - 'a');
r[i] = st[pt.last].len;
}
pt.clear();
pt.Init();
reverse(str, str + len);
for(int i = ; i < len; ++ i) {
pt.add(str[i] - 'a');
l[len - i - ] = st[pt.last].len;
}
for(int i = ; i < len; ++ i)
ans = max(ans, r[i] + l[i + ]);
printf("%d\n", ans);
return ;
}
2565
题目3 BZOJ2160 拉拉队排练
算法讨论：
首先建出回文自动机，然后排序，然后计算。话说这个题并不用这么麻烦的，好像Manacher直接就上，但是为了练习回文自动机嘛 。
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm> using namespace std; const int N = + ;
const int C = ;
const int mod = ;
typedef long long ll; ll k, ans = , cs[N];
int len, rank[N];
char str[N]; struct State {
int len, cnt, num, s, fail, next[C];
}st[N]; struct Ptree {
int n, sz, last; int newnode(int lens) {
st[sz].len = lens;
return sz ++;
} void Init() {
sz = n = last = ;
newnode(); newnode(-);
st[n].s = -;
st[].fail = ;
} int getfail(int x) {
while(st[n - st[x].len - ].s != st[n].s) x = st[x].fail;
return x;
} void count() {
for(int i = sz - ; i >= ; -- i)
st[st[i].fail].cnt += st[i].cnt;
} void add(int c) {
st[++ n].s = c;
int cur = getfail(last);
if(!st[cur].next[c]) {
int now = newnode(st[cur].len + );
st[now].fail = st[getfail(st[cur].fail)].next[c];
st[cur].next[c] = now;
st[now].num = st[st[now].fail].num + ;
}
last = st[cur].next[c];
st[last].cnt ++;
}
}pt; ll quickpow(ll a, ll b) {
ll res = ;
if(!b) return res;
while(b) {
if(b & ) res = res * a % mod;
a = a * a % mod;
b >>= ;
}
return res;
} int main() {
scanf("%d%lld", &len, &k);
scanf("%s", str);
pt.Init();
for(int i = ; i < len; ++ i)
pt.add(str[i] - 'a');
pt.count();
for(int i = ; i < pt.sz; ++ i) cs[st[i].len] ++;
for(int i = ; i <= len; ++ i) cs[i] += cs[i - ];
for(int i = ; i < pt.sz; ++ i) rank[cs[st[i].len] --] = i;
for(int i = pt.sz - ; i; -- i) {
if(!k) break;
if(st[rank[i]].len & ) {
if(k >= st[rank[i]].cnt) {
ans = 1LL * ans * quickpow(st[rank[i]].len, st[rank[i]].cnt) % mod;
k -= st[rank[i]].cnt;
}
else {
ans = 1LL * ans * quickpow(st[rank[i]].len, k) % mod;
k -= k;
}
}
}
printf("%lld\n", ans % mod);
return ;
}
2160
题目4 BZOJ2084
算法讨论：
首先满足条件的串对应位上的数字正好是相反的，而且一定是偶数长度的串。
变种Manacher(其实是暴力)
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm> using namespace std; const int N = + ;
typedef long long ll; ll ans = ;
int len, Mp[N << ];
char str[N], Ma[N << ]; int idx(char c) {
return c - '';
} void Manacher(char *s, int lens) {
int l = ;
Ma[l ++] = '$'; Ma[l ++] = '#';
for(int i = ; i < lens; ++ i) {
Ma[l ++] = s[i]; Ma[l ++] = '#';
}
Ma[l] = '!';
int Mx = , id = ;
for(int i = ; i < l; ++ i) {
/*
if(Mx > i) {
Mp[i] = min(Mp[2 * id - i], Mx - i);
}
else {
Mp[i] = 1;
}
*/
Mp[i] = ;
while((Ma[i - Mp[i]] == Ma[i + Mp[i]] && Ma[i - Mp[i]] == '#') || ((Ma[i - Mp[i]] != '#' && Ma[i + Mp[i]] != '#' && (idx(Ma[i - Mp[i]]) ^ idx(Ma[i + Mp[i]])) == ))) Mp[i] ++;
if(Mx < Mp[i] + i) {
Mx = Mp[i] + i;
id = i;
}
}
for(int i = ; i < l; ++ i) {
if(Ma[i] == '#') {
ans = (long long) ans + (Mp[i] - ) / ;
}
}
printf("%lld\n", ans);
} int main() {
scanf("%d%s", &len, str);
Manacher(str, strlen(str)); return ;
}
1294
题目5 Uva719 GlassBeads
题目大意：求一个串的字典序最小的循环串。
算法讨论：设原串长为S，把原串倍长后建立出SAM，然后在Sam上走S步，所在的位置就是最小循环串的开头。
代码：
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;
const int L = + ; int ans = ;
char str[L<<]; struct State{
int len, pre;
int next[]; State(){
len = pre = ;
memset(next, , sizeof next);
}
void clear(){
len = pre = ;
memset(next, , sizeof next);
}
}st[L<<]; struct SuffixAutomaton{
int sz, last; void Init(){
last = ;
sz = ;
for(int i = ; i < (L<<); ++ i)
st[i].clear();
st[].len = ; st[].pre = -;
sz ++;
}
void Extend(int c){
int cur = sz ++;
st[cur].len = st[last].len + ;
int p; for(p = last; p != - && !st[p].next[c]; p = st[p].pre)
st[p].next[c] = cur; if(p == -) st[cur].pre = ;
else{
int q = st[p].next[c];
if(st[q].len == st[p].len + ) st[cur].pre = q;
else{
int cle = sz ++;
st[cle].len = st[p].len + ;
st[cle].pre = st[q].pre;
for(int i = ; i < ; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != - && st[p].next[c] == q; p = st[p].pre)
st[p].next[c] = cle;
st[q].pre = st[cur].pre = cle;
}
}
last = cur;
}
}SAM; void Input(){
scanf("%s", str);
} void Output(){
printf("%d\n", ans);
} void Solve(){
int len = strlen(str);
SAM.Init();
for(int i = ; i < len; ++ i)
str[i + len] = str[i];
for(int i = ; i < (len<<); ++ i){
SAM.Extend(str[i] - 'a');
}
int p = ;
for(int i = ; i < len; ++ i){
for(int j = ; j < ; ++ j){
if(st[p].next[j]){
p = st[p].next[j];
break;
}
}
} ans = st[p].len - len + ;
} int main(){
int t;
scanf("%d", &t);
while(t --){
Input();
Solve();
Output();
}
return ;
}
UVa719
题目6 SPOJ LCS
题目大意：求两个串的最长公共子串。
算法讨论：把串1建立出SAM，串2在SAM上走。如果串2的当前字符在SAM上有出边，则len++,继续向下走。如果失配，则向后缀连接跳。
如果跳到-1，说明串1中没有这个字符，len变为0，从下一个开始走，如果有，就让Len 等于后缀连接点的Len+1，（这说明这之前的字符是可以匹配的）
然后再向下走一步。继续。
代码：
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cstdio> using namespace std; const int N = + ;
const int C = ; struct State {
int len, pre, next[C];
void clear() {
len = pre = ;
memset(next, , sizeof next);
}
}st[N << ]; struct SuffixAutomaton {
int sz, last; void Init() {
for(int i = ; i < (N << ); ++ i)
st[i].clear();
sz = last = ;
st[sz].len = ; st[sz].pre = -;
sz ++;
} void add(int c) {
int cur = sz ++, p;
st[cur].len = st[last].len + ;
for(p = last; p != - && !st[p].next[c]; p = st[p].pre)
st[p].next[c] = cur;
if(p == -) st[cur].pre = ;
else {
int q = st[p].next[c];
if(st[q].len == st[p].len + ) st[cur].pre = q;
else {
int cle = sz ++;
st[cle].pre = st[q].pre;
st[cle].len = st[p].len + ;
for(int i = ; i < C; ++ i)
st[cle].next[i] = st[q].next[i];
for(; p != - && st[p].next[c] == q; p = st[p].pre)
st[p].next[c] = cle;
st[q].pre = st[cur].pre = cle;
}
}
last = cur;
}
}sam; char str1[N], str2[N];
int len1, len2; int main() {
scanf("%s%s", str1, str2);
len1 = strlen(str1); len2 = strlen(str2);
sam.Init();
for(int i = ; i < len1; ++ i)
sam.add(str1[i] - 'a');
int ans = , p = , len = ;
for(int i = ; i < len2; ++ i) {
int idx = str2[i] - 'a';
if(st[p].next[idx]) {
len ++;
p = st[p].next[idx];
}
else {
while(p != - && !st[p].next[idx])
p = st[p].pre;
if(p == -) {
p = ; len = ;
}
else {
len = st[p].len + ;
p = st[p].next[idx]; //这句话没有写。
}
}
ans = max(ans, len);
}
printf("%d\n", ans);
return ;
}
LCS
题目7 SPOJ LCS2
题目大意：求多个串的最长公共子串。
算法讨论：首先，两两之前匹配，然后取min的做法是错误的。正确的思路应该是，把其中的一个串建立SAM，然后把其它的串放在上面跑，对于SAM的每个结点，要多
维护两个信息，一个是当前串匹配的最大值，一个是已经匹配完的串到当前点匹配的最小值，每次匹配完一个串之后，用按照拓扑序，用儿子更新父亲的最大值，让其可能的大。
最后在所有最小值中取一个最大值，就是答案。
代码：
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream> using namespace std; const int N = + ;
const int C = ; struct State {
int pre, len, next[C], nl, ml;
}st[N << ]; struct SuffixAutomaton {
int sz, last; void Init() {
sz = last = ;
st[sz].pre = -; st[sz].len = ;
st[sz].ml = ;
sz ++;
} void add(int c) {
int cur = sz ++, p;
st[cur].len = st[last].len + ;
st[cur].ml = st[last].ml + ;
for(p = last; p != - && !st[p].next[c]; p = st[p].pre)
st[p].next[c] = cur;
if(p == -) st[cur].pre = ;
else {
int q = st[p].next[c];
if(st[q].len == st[p].len + ) st[cur].pre = q;
else {
int cle = sz ++;
st[cle].pre = st[q].pre;
st[cle].len = st[p].len + ;
st[cle].ml = st[p].ml + ;
for(int i = ; i < C; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != - && st[p].next[c] == q; p = st[p].pre)
st[p].next[c] = cle;
st[q].pre = st[cur].pre = cle;
}
}
last = cur;
}
}sam; char str[N];
int ans, lens, cs[N], rk[N << ]; int main() {
int p, len;
scanf("%s", str);
lens = strlen(str);
sam.Init();
for(int i = ; i < lens; ++ i)
sam.add(str[i] - 'a');
for(int i = ; i < sam.sz; ++ i) cs[st[i].len] ++;
for(int i = ; i <= lens; ++ i) cs[i] += cs[i - ];
for(int i = ; i < sam.sz; ++ i) rk[cs[st[i].len] --] = i; while(scanf("%s", str) != EOF) {
lens = strlen(str);
p = ; len = ;
for(int i = ; i < lens; ++ i) {
int idx = str[i] - 'a';
if(st[p].next[idx]) {
len ++;
p = st[p].next[idx];
}
else {
while(p != - && !st[p].next[idx])
p = st[p].pre;
if(p == -) {
p = ; len = ;
}
else {
len = st[p].len + ;
p = st[p].next[idx];
}
}
st[p].nl = max(len, st[p].nl);
}
for(int i = sam.sz - ; i >= ; -- i) {
st[rk[i]].ml = min(st[rk[i]].ml, st[rk[i]].nl);
if(st[rk[i]].pre != -) {
st[st[rk[i]].pre].nl = max(st[st[rk[i]].pre].nl, st[rk[i]].nl);
}
st[rk[i]].nl = ;
}
}
for(int i = sam.sz - ; i >= ; -- i) {
ans = max(ans, st[i].ml);
}
printf("%d\n", ans);
return ;
}
LCS2
题目8 SPOJ NSUBSTR
题目大意：求一个串长度为i的子串出现次数的最大值。
算法讨论：SAM中每个结点有两个信息维护：len, pre，len是当前点可以接收的子串的最长长度，pre是失配后的后缀连接。除此之外，还有一个我们经常说的right集合。
这个题 就是求Right集合的大小，具体做法是，把当前串建立出SAM，然后在非复制出的节点上跑SAM，就是用原串跑原串的SAM，把跑到的结点的Right集合数++。
接着把SAM拓扑排序，可以用基数排序，按照len从大到小处理，每个点的后缀连接点加上这个点的Right集合的大小，就是这个后缀连接点的Right集合的大小。Right集合的大小
表示当前状态可以接收的所有子符串的出现的次数。然后我们用Right集合去更新答案，最后还要用F[i+1]去更新F[i]，可是我并不知道是为什么，而且不这样做的话，交上去也能A。
代码：
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm> using namespace std; const int N = + ;
const int C = ; struct State {
int len, pre, next[C];
void clear() {
len = pre = ;
memset(next, , sizeof next);
}
}st[N << ]; struct SuffixAutomaton {
int sz, last; void Init() {
for(int i = ; i < (N << ); ++ i) {
st[i].clear();
}
sz = last = ;
st[sz].len = ; st[sz].pre = -;
sz ++;
} void add(int c) {
int cur = sz ++, p;
st[cur].len = st[last].len + ;
for(p = last; p != - && !st[p].next[c]; p = st[p].pre)
st[p].next[c] = cur;
if(p == -) st[cur].pre = ;
else {
int q = st[p].next[c];
if(st[q].len == st[p].len + ) st[cur].pre = q;
else {
int cle = sz ++;
st[cle].pre = st[q].pre;
st[cle].len = st[p].len + ;
for(int i = ; i < C; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != - && st[p].next[c] == q; p = st[p].pre)
st[p].next[c] = cle;
st[q].pre = st[cur].pre = cle;
}
}
last = cur;
}
}sam; char str[N];
int len, cs[N], rk[N << ], rt[N << ], ans[N]; int main() {
int p, l;
scanf("%s", str);
len = strlen(str);
sam.Init();
for(int i = ; i < len; ++ i) sam.add(str[i] - 'a');
for(int i = ; i < sam.sz; ++ i) cs[st[i].len] ++;
for(int i = ; i <= len; ++ i) cs[i] += cs[i - ];
for(int i = ; i < sam.sz; ++ i) rk[cs[st[i].len] --] = i;
p = ; //以下求出了每个结点的right集合大小
for(int i = ; i < len; ++ i) {
p = st[p].next[str[i] - 'a'];
rt[p] ++;
}
for(int i = sam.sz - ; i >= ; -- i)
rt[st[rk[i]].pre] += rt[rk[i]];
for(int i = sam.sz - ; i >= ; -- i) {
l = st[rk[i]].len;
ans[l] = max(ans[l], rt[rk[i]]);
}
for(int i = ; i < len; ++ i)
ans[i] = max(ans[i], ans[i + ]);
for(int i = ; i <= len; ++ i)
printf("%d\n", ans[i]);
return ;
}
NSUBSTR
题目9 SPOJ SUBLEX
题目大意：把一个串的所有本质不同的子串按照字典序排序后，求第k个串是什么。
算法讨论：对原串建立自动机，然后对SAM拓扑排序，然后我们可以统计出从SAM中的每个结点开始DFS可以得到的子串数目是多少，搞出这个东西，我们就可以在SAM上走启发式的DFS了。。嘿嘿。注意这个东西可不是Right集合。两个东西有着本质的区别。
代码：
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm> using namespace std; const int L = + ;
const int C = ; struct State {
int len, pre, next[C];
}st[L << ]; struct SuffixAutomaton {
int sz, last; void Init() {
sz = last = ;
st[sz].pre = -;
st[sz].len = ;
sz ++;
} void add(int c) {
int cur = sz ++, p;
st[cur].len = st[last].len + ;
for(p = last; p != - && !st[p].next[c]; p = st[p].pre)
st[p].next[c] = cur;
if(p == -) st[cur].pre = ;
else {
int q = st[p].next[c];
if(st[q].len == st[p].len + ) st[cur].pre = q;
else {
int cle = sz ++;
st[cle].pre = st[q].pre;
st[cle].len = st[p].len + ;
for(int i = ; i < C; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != - && st[p].next[c] == q; p = st[p].pre)
st[p].next[c] = cle;
st[cur].pre = st[q].pre = cle;
}
}
last = cur;
}
}sam; char str[L];
int len, rt[L << ], rk[L << ], cs[L], num[L];
char que[]; int main() {
int p, Q, k;
scanf("%s", str);
len = strlen(str);
sam.Init();
for(int i = ; i < len; ++ i)
sam.add(str[i] - 'a');
for(int i = ; i < sam.sz; ++ i) cs[st[i].len] ++;
for(int i = ; i <= len; ++ i) cs[i] += cs[i - ];
for(int i = ; i < sam.sz; ++ i) rk[cs[st[i].len] --] = i;
p = ;
for(int i = ; i < len; ++ i) {
p = st[p].next[str[i] - 'a'];
rt[p] ++;
}
for(int i = sam.sz - ; i >= ; -- i)
rt[st[rk[i]].pre] += rt[rk[i]];
for(int i = sam.sz - ; i >= ; -- i)
num[i] = ;
for(int i = sam.sz - ; i >= ; -- i) {
for(int j = ; j < C; ++ j) {
num[rk[i]] += num[st[rk[i]].next[j]];
}
}
scanf("%d", &Q);
while(Q --) {
scanf("%d", &k);
p = ;
while(k) {
for(int j = ; j < C; ++ j) {
if(num[st[p].next[j]] >= k) {
putchar(j + 'a');
k --;
p = st[p].next[j];
break;
}
else {
k -= num[st[p].next[j]];
}
}
}
puts("");
}
return ;
}
SUBLEX
题目10 HDU 4436 string2int
题目大意：给出n个串，求这n个串所有不同子串组成的所有十进制数的和是多少，有前导0的去掉前导0，出现多次的只算一次，答案对2012取模。
算法讨论：多串建立自动机。中间用特殊的字符隔开。然后拓扑排序，从len由小到大处理。这个题自己是又T又Wa，并不知道是为什么。还要再思考思考。
代码：
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio> using namespace std; const int C = ;
const int N = + ;
typedef long long ll; struct State {
int pre, len, next[C];
void clear() {
pre = len = ;
memset(next, , sizeof next);
}
}st[N << ]; struct SuffixAutomaton {
int sz, last; void Init() {
for(int i = ; i < sz; ++ i) st[i].clear();
sz = last = ;
st[sz].pre = -; st[sz].len = ;
sz ++;
} void add(int c) {
int cur = sz ++, p;
st[cur].len = st[last].len + ;
for(p = last; p != - && !st[p].next[c]; p = st[p].pre)
st[p].next[c] = cur;
if(p == -) st[cur].pre = ;
else {
int q = st[p].next[c];
if(st[q].len == st[p].len + ) st[cur].pre = q;
else {
int cle = sz ++;
st[cle].pre = st[q].pre;
st[cle].len = st[p].len + ;
for(int i = ; i < C; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != - && st[p].next[c] == q; p = st[p].pre)
st[p].next[c] = cle;
st[q].pre = st[cur].pre = cle;
}
}
last = cur;
}
}sam; char str[N];
int lens, n, zz, ans, cr, p, Len;
int rk[N << ], cs[N], sum[N << ], cnt[N << ]; int main() {
while(scanf("%d", &n) != EOF) {
memset(sum, , sizeof sum);
memset(cnt, , sizeof cnt);
memset(cs, , sizeof cs);
memset(rk, , sizeof rk);
sam.Init(); Len = ;
while(n --) {
scanf("%s", str);
lens = strlen(str);
Len += lens;
for(int i = ; i < lens; ++ i)
sam.add(str[i] - '');
sam.add('?' - '');
Len += ;
}
ans = ;
cnt[] = ;
for(int i = ; i < sam.sz; ++ i) cs[st[i].len] ++;
for(int i = ; i <= Len; ++ i) cs[i] += cs[i - ];
for(int i = ; i < sam.sz; ++ i) rk[cs[st[i].len] --] = i;
for(int i = ; i < sam.sz; ++ i) {
p = rk[i];
for(int j = ; j < ; ++ j) {
if(p == && !j) continue;
if(st[p].next[j]) {
cr = st[p].next[j];
cnt[cr] = (cnt[cr] + cnt[p]) % ;
sum[cr] = (sum[cr] + sum[p] * + cnt[p] * j) % ;
}
}
ans = (ans + sum[p]) % ;
}
printf("%d\n", ans);
}
return ;
}
HDU 4436
题目11 BZOJ3998 TJOI 弦论
题目大意：把一个串的所有子串按照字典序排序，求第K个。不同的是，如果type = 1，则位置不同的相同的串是不同的串，如果type = 0，则位置不同的相同的串算一个。
算法讨论：对于type = 0则是自动机的长处。对于type = 1的也是自动机的长处，对于type = 0,每次我们让k --就好了，对于type = 1，我们每次让k 减去当前这个right集合的
大小，对于从某个点出发可以得到多少个子串，type = 0，就把num[i]的初始设为1，对于type = 1，就把num[i]的初始设为其right集合的大小 。然后正常计算就可以。
代码：
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring> using namespace std; const int N = + ;
const int C = ; struct State {
int pre, len, next[C];
}st[N << ]; char str[N];
int type, k, len;
int cs[N], rk[N << ], num[N << ], rt[N << ]; struct SuffixAutomaton {
int sz, last; void Init() {
sz = last = ;
st[sz].pre = -; st[sz].len = ;
sz ++;
} void add(int c) {
int cur = sz ++, p;
st[cur].len = st[last].len + ;
for(p = last; p != - && !st[p].next[c]; p = st[p].pre)
st[p].next[c] = cur;
if(p == -) st[cur].pre = ;
else {
int q = st[p].next[c];
if(st[q].len == st[p].len + ) st[cur].pre = q;
else {
int cle = sz ++;
st[cle].len = st[p].len + ;
st[cle].pre = st[q].pre;
for(int i = ; i < C; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != - && st[p].next[c] == q; p = st[p].pre)
st[p].next[c] = cle;
st[q].pre = st[cur].pre = cle;
}
}
last = cur;
}
}sam; int main() {
int p;
scanf("%s", str);
scanf("%d%d", &type, &k);
len = strlen(str);
sam.Init();
for(int i = ; i < len; ++ i)
sam.add(str[i] - 'a');
for(int i = ; i < sam.sz; ++ i) cs[st[i].len] ++;
for(int i = ; i <= len; ++ i) cs[i] += cs[i - ];
for(int i = ; i < sam.sz; ++ i) rk[cs[st[i].len] --] = i;
p = ;//求Right
for(int i = ; i < len; ++ i) {
p = st[p].next[str[i] - 'a'];
rt[p] ++;
}
for(int i = sam.sz - ; i >= ; -- i)
rt[st[rk[i]].pre] += rt[rk[i]];
//求num
if(type)
for(int i = sam.sz - ; i >= ; -- i)
num[rk[i]] = rt[rk[i]];
else
for(int i = sam.sz - ; i >= ; -- i)
num[i] = ;
num[] = ; rt[] = ;
for(int i = sam.sz - ; i >= ; -- i) {
for(int j = ; j < C; ++ j) {
num[rk[i]] += num[st[rk[i]].next[j]];
}
}
if(num[] < k) { puts("-1"); return ; }
p = ;
while(k) {
for(int j = ; j < C; ++ j) {
if(num[st[p].next[j]] >= k) {
if(type) k -= rt[st[p].next[j]];
else k --;
p = st[p].next[j];
putchar(j + 'a');
break;
}
else {
k -= num[st[p].next[j]];
}
}
}
return ;
}
BZOj 3998
题目12 BZOJ 2555 Subtrings
题目大意：对于一个字符串，有两个操作，一个是向当前串尾部加入一个字符串，另一个操作是询问某个串出现了多少次。强制在线。
算法讨论：首先，求某个串出现了多少次就是把这个串放在自动机上去跑，然后跑到的end结点的Right集合大小就是这个串出现的次数。
但是本题要求还有添加字符，我们不可能每一次都重新计算一下Right集合，所以我们要有一个支持在线修改Right并维护其大小的东西。
由于这东西有很强的树型结构，所以我们采用LInkCutTree来维护它。每次加入一个字符，就把这个字符的Right集合大小置为1.然后有设置pre指针的地方我们就Link，
如果有改变pre指针的地方我们就先Cut再Link，最后把某个串放在上面跑，输出end结点的val值就可以了。
这个题会了两个东西：
1、在Extend的时候求哪些点是有用的点(不是复制出来的点)，我原来求Right集合的有用点都是先建立SAM，再把原串放在上面跑，求有用的结点。
LinkCutTree在Link和Cut的时候就可以维护Right大小了。对于第一种方法，我们还要拓扑一下求Right集合大小。
2、用LinkCutTree维护Right集合，有一个好处是Splay中没有pushup。
代码：
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm> using namespace std; const int N = + ;
const int C = ; int sz, last, lens, n, top;
char str[N], ss[];
int fa[N << ], c[N << ][], val[N << ], add[N << ], sta[N << ];
bool rev[N << ]; struct State {
int len, pre, next[C];
}st[N << ]; void pushdown(int x) {
int l = c[x][], r = c[x][];
if(rev[x]) {
rev[x] ^= ; rev[l] ^= ; rev[r] ^= ;
swap(c[x][], c[x][]);
}
if(add[x]) {
val[l] += add[x]; val[r] += add[x];
add[l] += add[x]; add[r] += add[x];
add[x] = ;
}
} bool isroot(int x) {
return c[fa[x]][] != x && c[fa[x]][] != x;
} void rotate(int x) {
int y = fa[x], z = fa[y], l, r;
l = (c[y][] == x) ^ ; r = l ^ ;
if(!isroot(y)) {
c[z][(c[z][] == y) ^ ] = x;
}
fa[x] = z; fa[y] = x; fa[c[x][r]] = y;
c[y][l] = c[x][r]; c[x][r] = y;
} void splay(int x) {
top = ; sta[++ top] = x;
for(int i = x; !isroot(i); i = fa[i])
sta[++ top] = fa[i];
while(top) pushdown(sta[top --]);
while(!isroot(x)) {
int y = fa[x], z = fa[y];
if(!isroot(y)) {
if((c[z][] == y) ^ (c[y][] == x)) rotate(x);
else rotate(y);
}
rotate(x);
}
} void Access(int x) {
int t = ;
while(x) {
splay(x); c[x][] = t;
t = x; x = fa[x];
}
} int Findroot(int x) {
Access(x); splay(x);
while(c[x][]) x = c[x][];
return x;
} void Makeroot(int x) {
Access(x); splay(x); rev[x] ^= ;
} void Cut(int x) {
Access(x); splay(x);
val[c[x][]] -= val[x];
add[c[x][]] -= val[x];
c[x][] = fa[c[x][]] = ;
} void Link(int x, int y) {
fa[x] = y;
Access(y); splay(y);
val[y] += val[x]; add[y] += val[x];
} void decode(char *s, int mask) {
int le = strlen(s);
for(int j = ; j < le; ++ j) {
mask = (mask * + j) % le;
swap(s[mask], s[j]);
}
} void Init() {
sz = last = ;
st[sz].pre = -; st[sz].len = ;
sz ++;
} void Extend(int c) {
int cur = sz ++, p;
st[cur].len = st[last].len + ;
val[cur] = ;
for(p = last; p != - && !st[p].next[c]; p = st[p].pre)
st[p].next[c] = cur;
if(p == -) st[cur].pre = , Link(cur, );
else {
int q = st[p].next[c];
if(st[q].len == st[p].len + ) st[cur].pre = q, Link(cur, q);
else {
int cle = sz ++;
st[cle].pre = st[q].pre; Link(cle, st[q].pre);
st[cle].len = st[p].len + ;
for(int i = ; i < C; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != - && st[p].next[c] == q; p = st[p].pre)
st[p].next[c] = cle;
Cut(q); Link(q, cle); Link(cur, cle);
st[q].pre = st[cur].pre = cle;
}
}
last = cur;
} int main() {
int mask = ;
scanf("%d", &n);
scanf("%s", ss);
lens = strlen(ss);
Init();
for(int i = ; i < lens; ++ i)
Extend(ss[i] - 'A');
while(n --) {
scanf("%s%s", ss, str);
lens = strlen(str);
if(ss[] == 'A') {
decode(str, mask);
for(int i = ; i < lens; ++ i)
Extend(str[i] - 'A');
}
else if(ss[] == 'Q') {
decode(str, mask);
int p = ; bool flag = false;
for(int i = ; i < lens; ++ i) {
if(!st[p].next[str[i] - 'A']) {
flag = true; break;
}
p = st[p].next[str[i] - 'A'];
}
if(flag) {
puts(""); continue;
}
splay(p);
printf("%d\n", val[p]);
mask ^= val[p];
}
}
return ;
}
2555
题目13 HDU 4622
题目大意：
给一个串，询问l..r的不同子串个数。
算法讨论：
新加入一个字符，新增的不同子串数为st[cur].len - st[st[cut].pre].len。
对于询问，我们离线操作，左端点相同的我们只维护一个加字符，如果左端点不同，就定期重建自动机。
动态维护不同子串数，SMZ大神自己YY了一个做法，考虑加入一个结点会对多少条从根结点到当前结点的路径造成影响。
代码以SDOI2016的某个水题附上。
代码：
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio> using namespace std; const int N = + ;
const int C = ; int Ans = ; struct State {
int pre, len, next[C];
void clear() {
pre = len = ;
memset(next, , sizeof next);
}
}st[N << ]; struct SuffixAutomaton {
int sz, last; void Init() {
for(int i = ; i < sz; ++ i)
st[i].clear();
sz = last = ;
st[sz].len = ; st[sz].pre = -;
sz ++;
} void add(int c) {
int cur = sz ++, p;
st[cur].len = st[last].len + ;
for(p = last; p != - && !st[p].next[c]; p = st[p].pre)
st[p].next[c] = cur;
if(p == -) st[cur].pre = ;
else {
int q = st[p].next[c];
if(st[q].len == st[p].len + ) st[cur].pre = q;
else {
int cle = sz ++;
st[cle].pre = st[q].pre;
st[cle].len = st[p].len + ;
for(int i = ; i < C; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != - && st[p].next[c] == q; p = st[p].pre)
st[p].next[c] = cle;
st[q].pre = st[cur].pre = cle;
}
}
last = cur;
Ans = Ans + st[cur].len - st[st[cur].pre].len;
}
}sam; struct Query {
int l, r, id;
bool operator < (const Query &k) const {
if(l == k.l) return r < k.r;
return l < k.l;
}
}qs[]; int ans[], cs[N], rk[N << ], num[N << ];
char str[N]; int main() {
int t, Q;
scanf("%d", &t);
while(t --) {
scanf("%s", str + );
scanf("%d", &Q);
for(int i = ; i <= Q; ++ i) {
scanf("%d%d", &qs[i].l, &qs[i].r);
qs[i].id = i;
}
sort(qs + , qs + Q + );
for(int i = ; i <= Q; ++ i) {
if(qs[i].l == qs[i - ].l) {
for(int j = qs[i - ].r + ; j <= qs[i].r; ++ j)
sam.add(str[j] - 'a');
}
else {
sam.Init(); Ans = ;
for(int j = qs[i].l; j <= qs[i].r; ++ j)
sam.add(str[j] - 'a');
}
ans[qs[i].id] = Ans;
}
for(int i = ; i <= Q; ++ i)
printf("%d\n", ans[i]);
}
return ;
}
4622
附SMZ大神的另一个做法：SDOI2016 生成魔咒她的代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define maxn 200010
using namespace std; int n; int a[maxn]; struct Node{
int len, link;
map<int, int> nxt;
}st[maxn]; int root, size, last;
void init(){
root = size = last = ;
st[root].len = ;
st[root].link = -;
} long long ans; long long vis[maxn]; void Extend(int c){
int cur = ++ size, p = last;
st[cur].len = st[p].len + ;
for(; ~p && st[p].nxt[c] == ; p = st[p].link)
st[p].nxt[c] = cur, vis[cur] += vis[p];
ans += vis[cur];
if(p == -)
st[cur].link = root;
else{
int q = st[p].nxt[c];
if(st[q].len == st[p].len + )
st[cur].link = q;
else{
int clone = ++ size;
st[clone] = st[q];
st[clone].len = st[p].len + ;
vis[clone] = ;
for(; ~p && st[p].nxt[c] == q; p = st[p].link)
st[p].nxt[c] = clone, vis[clone] += vis[p], vis[q] -= vis[p];
st[q].link = st[cur].link = clone;
}
}
last = cur;
} int main(){
freopen("menci_incantation.in", "r", stdin);
freopen("menci_incantation.out", "w", stdout);
init();
vis[root] = ;
scanf("%d", &n);
for(int i = ; i <= n; i ++){
scanf("%d", &a[i]);
Extend(a[i]);
printf("%lld\n", ans);
}
return ;
}
SDOI 2016
题目14 百度之星2015年复赛 最强密码(提交入口：HDU 5262)
题目大意：
给定一个字符串，求最短的不是其子序列的串的长度和个数。
算法讨论：
序列自动机 + Dp。由于答案只在空节点进行累计，所以我们建立一个空的专门接受没有这个字符出边的节点，
然后在这个节点上进行答案统计就可以，我们从前向后走序列自动机，第一个更新这个节点长度的就是最短串的长度，
后面的节点如果走到这个节点，由于长度都比这个大，所以只会对其进行答案累计。
代码：
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
const int N = 100000 + 5;
const int C = 26;
const int mod = 1e9 + 7; int len;
char str[N];
int last[N], anslen[N], dp[N];
struct Node {
int next[C];
}st[N]; int main() {
int count = 0, T;
scanf("%d", &T);
while(T --) {
++ count;
printf("Case #%d:\n", count);
scanf("%s", str + 1);
len = strlen(str + 1);
for(int i = 0; i < C; ++ i) last[i] = len + 1;
for(int i = len; i >= 1; -- i) {
for(int j = 0; j < C; ++ j) st[i].next[j] = last[j];
last[str[i] - 'a'] = i;
}
for(int i = 0; i < C; ++ i) st[0].next[i] = last[i];
for(int i = 1; i <= len + 1; ++ i) anslen[i] = len + 1;
anslen[0] = 0; dp[0] = 1;
for(int i = 0; i <= len; ++ i) {
for(int j = 0; j < C; ++ j) {
int nxt = st[i].next[j];
if(anslen[i] + 1 < anslen[nxt]) {
anslen[nxt] = anslen[i] + 1;
dp[nxt] = dp[i];
}
else if(anslen[i] + 1 == anslen[nxt]) {
dp[nxt] += dp[i];
if(dp[nxt] >= mod) dp[nxt] -= mod;
}
}
}
printf("%d %d\n", anslen[len + 1], dp[len + 1]);
}
return 0;
}
题目15 HDU 3336
题目大意：
求一个串的所有前缀在这个串中的出现次数和，答案Mod10007
算法讨论：AC自动机
对于每个节点都是一个end结点，所以我们只要在原串的AC自动机上跑原串，像以往那样正常统计出现次数就可以了。
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue> using namespace std;
const int N = 200000 + 5;
const int C = 26;
const int mod = 10007;
typedef long long ll; char str[N];
int n;
ll ans = 0; struct Ac {
int sz;
int c[N][C], fail[N], end[N]; Ac() {
sz = 1;
}
void clear() {
sz = 1;
memset(c, 0, sizeof c);
memset(fail, 0, sizeof fail);
memset(end, 0, sizeof end);
} int idx(char cc) { return cc - 'a'; }
void insert(char *buf) {
int cur = 0, len = strlen(buf);
for(int i = 0; i < len; ++ i) {
int x = idx(buf[i]);
if(!c[cur][x]) c[cur][x] = sz ++;
cur = c[cur][x];
end[cur] ++;
}
}
void build() {
queue <int> q;
fail[0] = 0;
for(int i = 0; i < C; ++ i)
if(!c[0][i]) c[0][i] = 0;
else {
fail[c[0][i]] = 0;
q.push(c[0][i]);
}
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = 0; i < C; ++ i) {
if(!c[x][i]) c[x][i] = c[fail[x]][i];
else {
fail[c[x][i]] = c[fail[x]][i];
q.push(c[x][i]);
}
}
}
}
void query(char *buf) {
int cur = 0, len = strlen(buf);
for(int i = 0; i < len; ++ i) {
int x = idx(buf[i]);
cur = c[cur][x];
int tmp = cur;
while(tmp) {
if(end[tmp]) {
ans = ans + end[tmp];
if(ans >= mod) {
ans -= mod;
}
}
tmp = fail[tmp];
}
}
}
}ac; int main() {
int t;
scanf("%d", &t);
while(t --) {
scanf("%d", &n);
scanf("%s", str);
ac.insert(str);
ac.build();
ac.query(str);
printf("%lld\n", (ans + mod) % mod);
ans = 0;
ac.clear();
}
return 0;
}
题目16 BZOJ 2780
题目大意：
求一个串在多少个串中出现。
算法讨论：
后缀自动机。对多串建立广义后缀自动机，每个节点都要保存其在哪个串中出现的颜色信息。然后建立出Parent树，求出DFS序。
对于每个询问， 在自动机上先跑一遍，求出其到达的end结点，没有的就直接把答案设为0.
然后将询问全部离线，按照DFS右端点从小到大排序，然后再按照DFS序的顺序处理自动机上的每个结点，
这里用树状数组来维护区间和进行统计答案。有点莫队的思想。计算即可。
代码：
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector> using namespace std;
const int N = 100000 + 5;
const int C = 128; struct State {
int len, pre, next[C];
vector <int> color;
}st[N << 1]; struct SuffixAutomaton {
int sz, last;
void Init() {
last = sz = 1;
st[sz].pre = -1; st[sz].len = 0;
sz ++;
}
void add(int c, int ccc) {
int cur = sz ++, p;
st[cur].len = st[last].len + 1;
for(p = last; p != -1 && !st[p].next[c]; p = st[p].pre)
st[p].next[c] = cur;
if(p == -1) st[cur].pre = 1;
else {
int q = st[p].next[c];
if(st[q].len == st[p].len + 1) st[cur].pre = q;
else {
int cle = sz ++;
st[cle].pre = st[q].pre;
st[cle].len = st[p].len + 1;
for(int i = 0; i < C; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != -1 && st[p].next[c] == q; p = st[p].pre)
st[p].next[c] = cle;
st[q].pre = st[cur].pre = cle;
}
}
last = cur;
st[cur].color.push_back(ccc);
}
}sam; char str[N];
int n, m, cnt, tim, len;
int head[N << 1], in[N << 1], out[N << 1], lastins[N];
int ans[N], seq[N << 1], cc[N << 1];
struct Edge {
int from, to, next;
}edges[N << 1];
struct Query {
int id, l, r;
bool operator < (const Query &k) const {
return r < k.r;
}
}Q[N]; void insert(int f, int u) {
++ cnt;
edges[cnt].from = f; edges[cnt].to = u;
edges[cnt].next = head[f]; head[f] = cnt;
}
void dfs(int u) {
in[u] = ++ tim; seq[tim] = u;
for(int i = head[u]; i; i = edges[i].next)
dfs(edges[i].to);
out[u] = tim;
} int LowBit(int x) { return x & (-x); }
int query(int x) {
int res = 0;
for(int i = x; i > 0; i -= LowBit(i)) res += cc[i];
return res;
}
void update(int x, int v) {
for(int i = x; i < sam.sz; i += LowBit(i)) cc[i] += v;
} int main() {
scanf("%d%d", &n, &m);
sam.Init();
for(int i = 1; i <= n; ++ i) {
scanf("%s", str);
len = strlen(str);
for(int j = 0; j < len; ++ j)
sam.add(str[j], i);
sam.last = 1;//back to the root ....
}
for(int i = 1; i < sam.sz; ++ i)
if(st[i].pre != -1) insert(st[i].pre, i);
dfs(1);
for(int i = 1; i <= m; ++ i) {
scanf("%s", str);
len = strlen(str);
int p = 1; bool flag = false;
for(int j = 0; j < len; ++ j) {
if(!st[p].next[(int)str[j]]) { flag = true; break; }
else p = st[p].next[(int)str[j]];
}
Q[i].id = i;
if(flag) { Q[i].l = Q[i].r = -1; }
else { Q[i].l = in[p]; Q[i].r = out[p]; }
}
sort(Q + 1, Q + m + 1);
int cur = 1;
while(cur <= m && Q[cur].l == -1) ans[Q[cur].id] = 0, cur ++;
for(int i = 1; i < sam.sz; ++ i) {
for(int j = 0; j < (signed) st[seq[i]].color.size(); ++ j) {
int now = st[seq[i]].color[j];
update(i, 1);
if(lastins[now]) update(lastins[now], -1);
lastins[now] = i;
}
for(; Q[cur].r == i; ++ cur) ans[Q[cur].id] = query(Q[cur].r) - query(Q[cur].l - 1);
}
for(int i = 1; i <= m; ++ i) printf("%d\n", ans[i]);
return 0;
}
