Trie和KMP学习笔记
chinaxjh
2019-11-11 18:02:33
# Trie
## Part 1
### 用途
用来维护前缀，拓展到转二进制位后的$xor$最大值之类的问题，可以和$KMP$搭配成为$AC$自动机
**在编写过程中一定要注意内存大小**
## Part 2
### 模板
```cpp
void insert(string str)
{
int lenn,k,j;
lenn=str.size();
k=0;
for (j=0;j<lenn;j++)
{
if (!num[k][(int)str[j]-97])
{
len++;
num[k][(int)str[j]-97]=len;
}
k=num[k][(int)str[j]-97];
}
q[k]++;
}
int getans(string str)
{
int lenn,ans,k,j;
lenn=str.size();
ans=0; k=0;
for (j=0;j<lenn;j++)
{
if (!num[k][(int)str[j]-97]) break;
k=num[k][(int)str[j]-97];
ans+=q[k];//可根据需要更改，这里是求前缀个数
}
return ans;
}
```
## Part 3
### 例题
##### 前缀统计
[题目](https://www.acwing.com/problem/content/144/)
$Trie$模板题
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int num[N][27],q[N];
int n,m,i,lenn,j,len,ans,k;
string str;
int main()
{
cin>>n>>m;
for (i=1;i<=n;i++)
{
cin>>str;
lenn=str.size();
k=0;
for (j=0;j<lenn;j++)
{
if (!num[k][(int)str[j]-97])
{
len++;
num[k][(int)str[j]-97]=len;
}
k=num[k][(int)str[j]-97];
}
q[k]++;
}
for (i=1;i<=m;i++)
{
cin>>str;
lenn=str.size();
ans=0; k=0;
for (j=0;j<lenn;j++)
{
if (!num[k][(int)str[j]-97]) break;
k=num[k][(int)str[j]-97];
ans+=q[k];
}
printf("%d\n",ans);
}
}
```
##### 最大异或对
[题目](https://www.acwing.com/problem/content/145/)
$Trie$用在求解$xor$问题的常见类型
寻找在所有数中找两个数的最大$xor$值
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=40;
int num[1000005][4],str[N],f[100005][N];
int n,m,i,lenn,j,len,ans,k,t;
void fenjie(int t)
{
if (t==0) return;
lenn++;
fenjie(t/2);
f[i][32-lenn]=t%2;
lenn--;
}
void insert(int x)
{
int k,j;
k=0;
for (j=0;j<32;j++)
{
if (!num[k][f[x][j]])
{
len++;
num[k][f[x][j]]=len;
}
k=num[k][f[x][j]];
}
}
int getting(int x)
{
int k,i,kk,ans;
k=0; ans=0;
for (i=0;i<32;i++)
{
kk=1^f[x][i];
if (num[k][kk])
{
k=num[k][kk];
ans+=(1<<(31-i));
} else k=num[k][f[x][i]];
}
return ans;
}
int main()
{
cin>>n;
for (i=1;i<=n;i++)
{
cin>>t;
lenn=0;
fenjie(t);
insert(i);
}
for (i=1;i<=n;i++)
ans=max(ans,getting(i));
cout<<ans<<endl;
}
```
##### 最长异或值路径
[题目Acwing](https://www.acwing.com/problem/content/146/)
[题目luogu](https://www.luogu.org/problem/P4551)
只要计算儿子节点到根节点的路径异或的值$d[x]$，然后发现对于节点$x$,$y$,$d[x]$ $xor$ $d[y]$的结果就是他们之间路径上的异或总和，到根节点的相同部分就抵消了，可以转换成上面一题，寻找所有$d[x]$中$xor$值最大的结果
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=40;
const int NN=300005;
int a[NN],b[NN],nxt[NN],las[NN],fa[NN],num[1000005][4],str[N],f[100005][N],d[NN];
int n,m,i,lenn,j,len,ans,k,t,elen,x,y,z;
void fenjie(int t)
{
if (t==0) return;
lenn++;
fenjie(t/2);
f[i][32-lenn]=t%2;
lenn--;
}
void insert(int x)
{
int k,j;
k=0;
for (j=0;j<32;j++)
{
if (!num[k][f[x][j]])
{
len++;
num[k][f[x][j]]=len;
}
k=num[k][f[x][j]];
}
}
int getting(int x)
{
int k,i,kk,ans;
k=0; ans=0;
for (i=0;i<32;i++)
{
kk=1^f[x][i];
if (num[k][kk])
{
k=num[k][kk];
ans+=(1<<(31-i));
} else k=num[k][f[x][i]];
}
return ans;
}
void add(int x,int y,int z)
{
elen++;
a[elen]=y;
b[elen]=z;
nxt[elen]=las[x];
las[x]=elen;
}
void dfs(int x)
{
int i;
for (i=las[x];i;i=nxt[i])
if (a[i]!=fa[x])
{
fa[a[i]]=x;
d[a[i]]=d[x]^b[i];
dfs(a[i]);
}
}
int main()
{
cin>>n;
for (i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs(1);//Acwing上是0
for (i=1;i<=n;i++)
{
t=d[i];
lenn=0;
fenjie(t);
insert(i);
ans=max(ans,getting(i));
}
cout<<ans<<endl;
}
```
# KMP
## Part 1
### 用途
两个字符串匹配的最快匹配算法，时间为O(n)
## Part 2
### 模板
[P3375 【模板】KMP字符串匹配](https://www.luogu.org/problem/P3375)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
int n,m,j,i,nxt[N+5];
char a[N+5],b[N+5];
int main()
{
cin>>a+1;
cin>>b+1;
n=strlen(a+1);
m=strlen(b+1);
nxt[1]=0;
j=0;
for (i=1;i<m;i++)
{
while (j>0&&b[j+1]!=b[i+1]) j=nxt[j];
if (b[j+1]==b[i+1]) j++;
nxt[i+1]=j;
}
j=0;
for (i=0;i<n;i++)
{
while (j>0&&a[i+1]!=b[j+1]) j=nxt[j];
if (a[i+1]==b[j+1]) j++;
if (j==m)
{
printf("%d\n",i-m+2);
j=nxt[j];
}
}
for (i=1;i<=m;i++)
printf("%d ",nxt[i]);
}
```
## Part 3
### 例题
[P4391 Radio Transmission 无线传输](https://www.luogu.org/problem/P4391)
$KMP$自我匹配板子题
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
int n,m,j,i,ans,nxt[N+5];
char b[N+5];
int main()
{
cin>>m;
cin>>b+1;
nxt[1]=0;
j=0;
for (i=1;i<m;i++)
{
while (j>0&&b[j+1]!=b[i+1]) j=nxt[j];
if (b[j+1]==b[i+1]) j++;
nxt[i+1]=j;
}
ans=m-nxt[m];
printf("%d",ans);
}
```