rockdu
Bomboslav set up a branding agency and now helps companies to create new logos and advertising slogans. In term of this problems, slogan of the company should be a non-empty substring of its name. For example, if the company name is "hornsandhoofs", then substrings "sand" and "hor" could be its slogans, while strings "e" and "hornss" can not.
Sometimes the company performs rebranding and changes its slogan. Slogan A is considered to be cooler than slogan B if B appears in Aas a substring at least twice (this occurrences are allowed to overlap). For example, slogan A = "abacaba" is cooler than slogan B = "ba", slogan A = "abcbcbe" is cooler than slogan B = "bcb", but slogan A = "aaaaaa" is not cooler than slogan B = "aba".
You are given the company name w and your task is to help Bomboslav determine the length of the longest sequence of slogans s1, s2, ..., sk, such that any slogan in the sequence is cooler than the previous one.
The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the company name that asks Bomboslav to help. The second line contains the string w of length n, that consists of lowercase English letters.
Print a single integer — the maximum possible length of the sequence of slogans of the company named w, such that any slogan in the sequence (except the first one) is cooler than the previous
3abc
1
5ddddd
5
11abracadabra
3
集训考题，这里就放一个线段树可持久化合并的题解吧。
官方题解：
如果一个 K 级的字符串含有一个出现过两次以上 K-1 级的字符串 T，并且这个 K
级字符串的开头或者结尾的字母被删除后 T 还是能够出现两次及以上，那么删除后的
字符串依旧是一个 K 级字符串。
也就是说如果我们有一个 K 级字符串，那么这个 K 级字符串一定包含一个开头和
结尾都是字符串 T 的 K 级字符串。
继续对于题目分析我们可以得到，如果我们有一个 K 级字符串，那么一定有一个
开头和结尾都是同一个 K-1 级字符串的字符串，而且这个 K-1 级字符串的开头和结尾
都是 K-2 级字符串，而且这个 K-2 级字符串的开头和结尾都是 K-3 级字符串……这样
一直到空串为止。
那么我们可以先对整个字符串建立后缀自动机。通过后缀自动机生成的 Fail 树我
们可以方便得对于一个字符串的一个后缀出现的位置进行统计。首先我们可以先递推
出 Fail 树上每个节点对应的所有子串在原串中出现位置的结尾的集合。对于一个字符
串 A，如果它的开头和结尾都是比同一个它低一个等级的字符串 B，那么根据后缀自
动机的性质可得——
B 在后缀自动机中一定和 A 没有对应同一个节点（因为出现的位置集合一定不同，
而且 A 出现位置结尾的集合真包含于 B 出现位置的结尾的集合）。
B 对应的节点在 Fail 树中一定是 A 对应的节点的祖先（因为 B 是 A 的后缀）。
所以我们只关注后缀自动机每个节点对应的等级最高中长度最短的子串即可。
我们只需要判断这个节点的所有祖先中等级最高的串是否在当前节点对应的子串
中出现过两次以上即可，如果是那么当前节点的等级加一，否则当前节点的等级就等
于这个最高等级（因为有包含关系）。
我们考虑使用线段树可持久化合并来求出每个树上节点对应的出现位置集合。判
断是否出现过两次以上就变成了线段树区间求和了。最终复杂度 O(NlogN)。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn = 4e5 + 5;
int l;
namespace SGT {
int rt[maxn], cnt;
const int L = 0, R = 1;
struct node {
int sum, ch[2];
}t[maxn * 64];
void push_up(int rt) {
t[rt].sum = t[t[rt].ch[L]].sum + t[t[rt].ch[R]].sum;
}
void add(int p, int tl, int tr, int & rt) {
if(!rt) rt = ++cnt;
if(tl == tr) return t[rt].sum = 1, void();
int mid = tl + tr >> 1;
if(p <= mid) add(p, tl, mid, t[rt].ch[L]);
else add(p, mid + 1, tr, t[rt].ch[R]);
push_up(rt);
}
int merge(int x, int y) {
if(x) t[++cnt] = t[x], x = cnt;
if(!x || !y) return x + y;
t[x].ch[L] = merge(t[x].ch[L], t[y].ch[L]);
t[x].ch[R] = merge(t[x].ch[R], t[y].ch[R]);
return push_up(x), x;
}
int query(int l, int r, int tl, int tr, int rt) {
if(!rt) return 0;
if(l == tl && r == tr) return t[rt].sum;
int mid = tl + tr >> 1;
if(r <= mid) return query(l, r, tl, mid, t[rt].ch[L]);
else if(l > mid) return query(l, r, mid + 1, tr, t[rt].ch[R]);
else return query(l, mid, tl, mid, t[rt].ch[L]) +
query(mid + 1, r, mid + 1, tr, t[rt].ch[R]);
}
}
int trie[maxn][26], len[maxn], fa[maxn];
int last, cnt, prs[maxn], ans[maxn], mx[maxn];
char s[maxn];
void add(char x, int pos) {
int id = x - 'a';
int p = last, np = ++cnt;
last = np, len[np] = len[p] + 1;
SGT::add(pos, 0, l, SGT::rt[np]);
prs[np] = pos;
while(p && !trie[p][id])
trie[p][id] = np, p = fa[p];
if(!p) fa[np] = 1;
else {
int q = trie[p][id];
if(len[q] == len[p] + 1) fa[np] = q;
else {
int lca = ++cnt;
fa[lca] = fa[q], fa[q] = fa[np] = lca;
len[lca] = len[p] + 1, prs[lca] = prs[q];
memcpy(trie[lca], trie[q], sizeof(trie[q]));
while(p && trie[p][id] == q)
trie[p][id] = lca, p = fa[p];
}
}
}
int tot[maxn], tp[maxn];
int main() {
last = cnt = 1;
scanf("%d", &l);
scanf("%s", s);
l = strlen(s), SGT::rt[1] = ++SGT::cnt;
for(register int i = 0; i < l; ++i)
add(s[i], i);
for(register int i = 1; i <= cnt; ++i) ++tot[len[i]];
for(register int i = 1; i <= l; ++i) tot[i] += tot[i - 1];
for(register int i = 1; i <= cnt; ++i)
tp[tot[len[i]]--] = i;
for(register int i = cnt; i >= 2; --i)
SGT::rt[fa[tp[i]]] = SGT::merge(SGT::rt[fa[tp[i]]], SGT::rt[tp[i]]);
for(register int i = 2; i <= cnt; ++i) {
using namespace SGT;
int nw = tp[i], p = mx[fa[nw]], tmp = 0;
if(fa[nw] == 1) ans[nw] = 1, mx[nw] = nw;
else
if((tmp = SGT::query(prs[nw] - len[nw] + 1 + len[fa[p]], prs[nw] - 1, 0, l, SGT::rt[p])) > 0)
ans[nw] = ans[p] + 1, mx[nw] = nw;
else
mx[nw] = p;
}
int nans = 0;
for(register int i = 1; i <= cnt; ++i)
nans = max(nans, ans[i]);
printf("%d", nans);
return 0;
}
没有帐号? 立即注册