Border树
参考：https://zhuanlan.zhihu.com/p/546135224
芝士?️
boder树：将next[i]作为i的父结点建成的树
-
同时作为S的前缀和后缀的字符串t在S中出现的次数？
在border树中，结点i的子树大小是S[1..i]在S中出现的总次数
-
同时作为S的前缀和后缀的字符串总共有哪些？
由定义知next[n]是满足条件的最长字符串，那么next[next[n]]就是满足条件的次长字符串….以此类推。所以，同时作为前缀和后缀的字符串是border树上所有的祖先结点对应的前缀串。
例题
例题1: 牛客28738F 葫芦和斌斌的字符串1
一句话题解：
对S建立border树，
从s[n]对应结点开始往上走[满足同时为前后缀]，
走到第一个[满足最长]子树size≥k[满足出现至少k次]的结点对应的前缀即为答案。
//牛客28738F 葫芦和斌斌的字符串1
//boder树：将next[i]作为i的父结点
//在border树中，结点i的子树大小是S[1..i]在S中出现的总次数
//by dttttttt
//2023/10/27
#include<iostream>
#include<vector>
using namespace std;
const int N=1e6+5;
int n,k,nxt[N],sz[N];
vector<int>to[N];
string s;
void get_next(){
nxt[1]=0;
for(int i=2,j=0;i<=n;++i){ //这里i要从2开始
while(j && s[j+1]!=s[i]) j=nxt[j];
if(s[j+1]==s[i]) ++j;
nxt[i]=j;
}
}
void build_border(){
for(int i=1;i<=n;++i)
to[nxt[i]].push_back(i);
}
void dfs(int u){
sz[u]=1;
for(int v:to[u]){
dfs(v);
sz[u]+=sz[v];
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>k;
cin>>s;
s='0'+s; //右移一位，为了下标从1开始
get_next(); //求kmp的next数组
build_border(); //建立border树
dfs(0); //求子树大小
int cur=n;
//从n开始往上走统计答案
/*
具体来说，next[n]同时是S的前缀和后缀，并且是最长的
则next[next[n]]也是S的前缀和后缀，并且是次长的
一直这么找可以找到满足同时是S的前缀和后缀的所有字符串，并且是越来越短的
接着我们要解决如何计算一个串在S中出现的次数这个问题：
以next[i]为i的父结点建立border树之后，一个结点i的子树的大小就是S[1..i]在S中出现的次数
理解:对于S的任意前缀S[1...i]，
它的所有的满足条件（指同时是前后缀）的后缀S[x..i]对应的前缀S[1..y]
(S[1..y]=S[x..i])
都是它的祖先结点（因为首先最长的那个是直接的父亲结点，次长的是父亲的父亲...）
结点i的子树里的结点，是以S[1..i]为后缀的所有结点，也就是S[1..i]出现的次数
*/
bool tag=0;
while(cur){
if(sz[cur]>=k){
tag=1;
break;
}
cur=nxt[cur];
//我们要找到深度最深的点，使得子树大小大于等于k,这是个树链上的二分问题，可以使用树上倍增来解决
}
if(!tag){
cout<<-1<<endl;
}
else{
cout<<s.substr(1,cur)<<endl;
}
return 0;
}
例题2: 牛客28738G 葫芦和斌斌的字符串2
在1的基础上，增加了多次查询和动态加点
- 多次查询
直接倍增爬树就行 - 动态加点
先把加的点都离线下来，算一个dfs序，在dfs序上动态加值（比如说，已经在树里的点值为1，还没加的为0）。于是把子树size的问题转换成子树和的问题，可以在dfs序上用树状数组or线段树处理。
//牛客28738G 葫芦和斌斌的字符串2
/*
在1的基础上，增加了多次查询和动态加点
1. 多次查询
直接倍增爬树就行
2. 动态加点
先把加的点都离线下来，算一个dfs序，在dfs序上动态加值（比如说，已经在树里的点值为1，还没加的为0）
于是把子树size的问题转换成子树和的问题，可以在dfs序上用树状数组or线段树处理
*/
//by dttttttt
//2023/10/27
#include<iostream>
#include<vector>
using namespace std;
const int N=1e6+5;
int n,m,k,nxt[N],sz[N],dfsn[N],L[N],R[N],dfs_tot=-1,f[N][21],sum[N],cur_n;
int added[N];
vector<int>to[N];
string s;
/*
dfsn[i]:dfs序为i的结点是谁,这题最后用不上
L[i]:结点i的dfs序
R[i]:结点i的子树中最大的dfs序
则结点i的子树在dfs序上对应的区间就是 [Li,Ri]
f[N][20]:倍增数组
sum[]:树状数组
*/
void get_next(){
nxt[1]=0;
for(int i=2,j=0;i<=n;++i){ //这里i要从2开始
while(j && s[j+1]!=s[i]) j=nxt[j];
if(s[j+1]==s[i]) ++j;
nxt[i]=j;
}
}
void build_border(){
for(int i=1;i<=n;++i)
to[nxt[i]].push_back(i);
}
int lowbit(int x){
return x&(-x);
}
int get_sum(int x){
int ret=0;
while(x){
ret+=sum[x];
x-=lowbit(x);
}
return ret;
}
void update(int x,int d){
while(x<=n){
sum[x]+=d;
x+=lowbit(x);
}
}
void dfs(int u){
L[u]=++dfs_tot;
dfsn[dfs_tot]=u;
for(int v:to[u]){
f[v][0]=u;
for(int i=1;i<21;++i)
f[v][i]=f[f[v][i-1]][i-1]; //这里需要放在dfs(v)的前面
dfs(v);
}
R[u]=dfs_tot;
}
struct query{
int op;
int k;
}q[N];
int calc(int l,int r){
int ret=0;
for(int i=l;i<=r;++i)
if(added[i]) ++ret;
return ret;
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
cin>>s;
cur_n=n;
s='0'+s; //右移一位，为了下标从1开始
for(int i=1;i<=m;++i){
cin>>q[i].op;
if(q[i].op==1){
char c;
cin>>c;
s.push_back(c);
++n;
}
else
cin>>q[i].k;
}
get_next(); //求kmp的next数组
build_border(); //建立border树
dfs(0); //求dfs序和倍增数组
//初始化树状数组：
for(int i=1;i<=cur_n;++i){
update(L[i],1);
}
for(int j=1;j<=m;++j){
if(q[j].op==1){
++cur_n;
update(L[cur_n],1);
continue;
}
k=q[j].k;
int now=cur_n;
for(int i=20;i>=0;--i){
int t=f[now][i];
if(t==0 || get_sum(R[t])-get_sum(L[t]-1)>=k)
continue;
now=f[now][i];
}
now=f[now][0];
if(!now) cout<<-1<<endl;
else cout<<now<<endl;
}
return 0;
}