kmp&字典树2 - “秋月春风等闲度”
2026-07-20 08:08:11
发布于：浙江
自主学习笔记类产物
“今年欢笑复明年，秋月春风等闲度。”——《琵琶行》
——————————————————————————————————————————
失配树
感觉今天下午是状态最差的一个下午了。
这道题目的思路是这样的：
我们需要通过套nxt去枚举出每一个前缀的所有border。这些border会组成一条链。
而一堆链会组成一棵树。
我们来描述一下这颗树的形态：树有很多个分支，每一个叶子节点都是一个前缀的长度，对于x，它的父亲节点编号会是：nxt[x-1]（关于为什么x-1：因为string从0开始）
当然这并不代表一共会有n条链，因为一个前缀有可能既是前缀又是border。
我们要找两个前缀的最长公共border，很容易就能联想最近公共祖先。
所以我们只要求lca(p,q)即可。
另：叶子节点都只是前缀，而不是Bourdor。
代码实现会有一点点问题，我先把AC的贴一下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int nxt[N],f[N],deep[N];
int f1[N][33];
vector<int>v[N];
void dfs(int x,int fa){
deep[x]=deep[fa]+1;
f1[x][0]=fa;
for(int i=1;i<=30;i++)f1[x][i]=f1[f1[x][i-1]][i-1];
for(int i=0;i<v[x].size();i++){
int to=v[x][i];
if(to==fa)continue;
dfs(to,x);
}
}
int lca(int a,int b){
if(deep[a]<deep[b])swap(a,b);
int len=deep[a]-deep[b];
for(int i=0;i<=30;i++){
if(len>>i&1)a=f1[a][i];
}
if(a==b)return a;
for(int i=30;i>=0;i--){
if(f1[a][i]==f1[b][i])continue;
a=f1[a][i];
b=f1[b][i];
}
return f1[a][0];
}
int main(){
string s;
cin>>s;
int j=1,len=0;
while(j<s.size()){
if(s[j]==s[len]){
nxt[j++]=++len;
}else{
if(len==0)j++;
else len=nxt[len-1];
}
}
for(int i=1;i<=s.size();i++){
f[i]=nxt[i-1];
v[nxt[i-1]].push_back(i);
}
dfs(0,0);
int m;
cin>>m;
for(int i=1;i<=m;i++){
int p,q;
cin>>p>>q;
int sum=lca(p,q);
if(sum==p||sum==q)cout<<f[sum]<<'\n';
else cout<<sum<<'\n';
}
return 0;
}
是这样的：注意到我只加了一条单向边。
如果加双向边2e6的数据会因为vector使用和其他预处理相关操作TLE
https://www.xinyoudui.com/ac/contest/747011272000BED0906D45/problem/8276
这道题是一个在kmp基础上修改一丢丢的板子题。但是我挂了点分，所以我把它弄出来写一下会错的点。注意到这是我的代码：（它是正确的）
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int nxt[N];
int main(){
int n,m;
cin>>n>>m;
string a,b;
cin>>a>>b;
int j=1;
int len=0;
while(j<b.size()){
if(b[j]==b[len]){
nxt[j++]=++len;
}else{
if(len==0)j++;
else len=nxt[len-1];
}
}
int i;
i=j=0;
int q=-1;
int cnt=0;
while(i<a.size()){
if(a[i]==b[j]){
i++,j++;
}else{
if(j==0)i++;
else j=nxt[j-1];
}
if(j==b.size()){
if(i-j<=q)continue;
cnt++;
q=i-1;
}
}
cout<<cnt;
return 0;
}
要点：q=-1（这是因为i-j可能等于0，如果将q初始化为0它就不会计算这种情况）
https://www.luogu.com.cn/problem/P4551
这道题的思路是：将n个节点道根节点的路径异或值全部记录到一个数组中，然后用这个数组中所有数的二进制建trie树，再用贪心思想：对于每个数都尽量找与当前相反的路径（0找1，1找0）
放一下代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct Node{
ll z,q;
};
vector<Node>v[N];
ll dis[N];
int tri[N*32][3],nxt;
void dfs(int x,int fa,int now){
dis[x]=now;
for(int i=0;i<v[x].size();i++){
int to=v[x][i].z;
if(to==fa)continue;
dfs(to,x,now^v[x][i].q);
}
}
void ins(int x){
int p=0;
for(int i=30;i>=0;i--){
int c=x>>i&1;
if(!tri[p][c])tri[p][c]=++nxt;
p=tri[p][c];
}
return;
}
int q(int x){
int p=0;
int ans=0;
for(int i=30;i>=0;i--){
int xx=x>>i&1;
if(tri[p][!xx])ans|=(1<<i),p=tri[p][!xx];
else p=tri[p][xx];
}
return ans;
}
int main(){
int n;
cin>>n;
for(int i=1;i<n;i++){
int u,vv,w;
cin>>u>>vv>>w;
v[u].push_back({vv,w});
v[vv].push_back({u,w});
}
dfs(1,0,0);
ins(dis[1]);
int ans=0;
for(int i=2;i<=n;i++){
ans=max(ans,q(dis[i]));
ins(dis[i]);
}
cout<<ans;
return 0;
}
这里空空如也
有帮助，赞一个