应用：
1.前缀问题
2.异或问题（转化为前缀问题）
3.查询问题
思想：
将要进行匹配的字符串化为一颗树
字符为边，在结束位置统计该串的全部信息
操作：插入，查询，删除.etc
ac:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=1e4+;
const int Z=;
int n,t,temp;
int trie[maxn*Z*Z][Z];//该写法调用快，但是占用空间大，视情况而定！！！trie数组节点数！！！
char num[Z];
bool isword[maxn*Z*Z],judge;
inline void insert()
{
int len=strlen(num+),pos=;
for(int i=;i<=len;i++){ int v=trie[pos][ num[i]-'' ];
//printf("i%d v%d\n",i,v); if(!v){//没有这个店->新建
trie[pos][num[i]-'']=++temp;
pos=temp;//！！注意不要提前给pos赋值！！
// if(i==10)printf("i=10:v%d\n",v);
}
else pos=v;//有这个点->继续 if(isword[pos])judge=;//该串包含某串 if(i==len){//到达字符串结尾，进行信息统计
isword[pos]=; if(v)judge=;//表示该串是某串的前缀
}
}
}
int main()
{
scanf("%d",&t);
while(t--){
memset(trie,,sizeof(trie));
memset(isword,,sizeof(isword));
judge=;temp=;//更新数据的问题 scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",num+);
insert();
}
if(!judge)printf("YES\n");
else printf("NO\n");
}
return ;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector>
using namespace std;
/*template<typename T>
inline void read(T &a){
a=0;T b=1;char x=getchar();
while(x<'0'||'9'<x){
if(x=='-')b=-1;
x=getchar();
}
while('0'<=x&&x<='9'){
a=(a<<1)+(a<<3)+x-'0';
x=getchar();
}
a*=b;
}
char C[50];
int temp;
template<typename T>
inline void write(T a){
if(a<0){
putchar('-');
a=-a;
}
do{
C[++temp]=a%10+'0';
a/=10;
}while(a);
while(temp)putchar(C[temp--]);
}*/ const int maxn=1e6+;
int to[maxn][],n,m,cnt,p;
vector<int >s[maxn];
char ch[];
bool vis[maxn];
inline void insert(int p){
int u=;int len=strlen(ch+);
for(int i=;i<=len;i++){
int v=ch[i]-'a';
if(!to[u][v])to[u][v]=++cnt;
u=to[u][v];
s[u].push_back(p);
}
}
inline int query(int p){ int u=;int len=strlen(ch+);
for(int i=;i<=len;i++){
int v=ch[i]-'a';
if(!to[u][v])return ;
u=to[u][v];
}
if(!vis[u]){sort(s[u].begin(),s[u].end());vis[u]=;}
return s[u].end()-lower_bound(s[u].begin(),s[u].end(),p);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%s%d",ch+,&p);
insert(p);
} for(int i=;i<=m;i++){
scanf("%s%d",ch+,&p);
printf("%d\n",query(p));
}
return ;
}
max xor:
思路，直接暴力很简单，但是非常慢，
发现一个性质，就是a xor b，每一位不一样的越多结果越大
所以想到trie树，我们把原来的数从32~1位建trie树，注意高位在前（不用担心会出现模式
串不够长的情况），保证结果最大，
查询时找 相反的边，实在没有就走相同的边，结果一定不会更差，
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=32e5+;
int to[maxn][],vis[maxn],cnt;
int n,m,num;
inline void insert(int p){
int u=;
for(int i=;i>=;i--){//取出p的32~1位
bool v=p&(<<i);
if(!to[u][v])to[u][v]=++cnt;
u=to[u][v];
}
}
inline int query(int p){
int u=,ans=;
for(int i=;i>=;i--){//取出p的32~1位
bool v=p&(<<i);
if(to[u][!v]){
u=to[u][!v];
ans=(ans<<|);
}
else {
u=to[u][v];
ans<<=;
}
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&num);
insert(num);
}
scanf("%d",&m);
for(int i=;i<=m;i++){
scanf("%d",&num);
printf("%d\n",query(num));
}
return ;
}
最长 xor路径：
利用了xor的与自己是互逆运算的性质，
我们维护一个数组，track[i]表示节点i到根节点的 xor值
最后每个节点询问它和已知节点（到根的xor路径值）的最大xor值
并且插入该值即可：
ac：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=32e5+; int first[maxn],next[maxn*],to[maxn*],w[maxn*],edge_count;
inline void add(int x,int y,int z){
edge_count++;
to[edge_count]=y;
w[edge_count]=z;
next[edge_count]=first[x];
first[x]=edge_count;
}
int track[maxn];
void dfs(int u,int fa){
for(int i=first[u];i;i=next[i]){
int v=to[i];
if(v==fa)continue; track[v]=track[u]^w[i];
dfs(v,u);
}
}
int e[maxn][],cnt;
inline void insert(int x){
int u=;
for(int i=;i>=;i--){//取出32~1位
bool v=x&(<<i);
if(!e[u][v])e[u][v]=++cnt;
u=e[u][v];
}
}
inline int query(int x){
int u=;
int ans=;
for(int i=;i>=;i--){
bool v=x&(<<i);
if(e[u][v^]){
u=e[u][v^];
ans=(ans<<|);
}
else{
u=e[u][v];
ans<<=;
}
}
return ans;
}
int n,ans;
int main(){
scanf("%d",&n);
for(int i=,u,v,q;i<n;i++){
scanf("%d%d%d",&u,&v,&q);
add(u,v,q);add(v,u,q);
}
dfs(,);
for(int i=;i<=n;i++){
ans=max(ans,query(track[i]));
insert(track[i]);
}
printf("%d",ans);
return ;
}
离线处理两个串的最长前缀O(nlogn)（注意数组越界问题）
：
/*问题描述
给出一些串，多组询问求两个串的最长公共前缀。字符串总长 < 10^6。
输入格式
第一行一个整数n，表示字符串的个数。
接下来n行，每行一个字符串（字符串不含空格）。
第n+2行一个整数m，表示询问总数。
接下来m行，每行两个整数a,b,表示询问第a个字符串和第b个字符串的最长公共前缀的长度。
输出格式
输出共m行，对于每个询问输出最长的公共前缀的长度
输入样例
5
abcdef
abcd
acd
cade
abcdef
4
1 2
2 3
1 5
3 4
输出样例
4
1
6
0
限制与约定
1<= m < 10^6
时间限制：1s
空间限制：256MB*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=1e6+;
char ch[maxn];
int n,m,to[maxn][],cnt,vis[maxn],maxdeep;
//vis[i]表示字符串i在trie树中位置
inline void insert(int p){
int u=;int len=strlen(ch+);
maxdeep+=len;
for(int i=;i<=len;i++){
int v=ch[i]-'a';
if(!to[u][v])to[u][v]=++cnt;
u=to[u][v];
}
vis[p]=u;
//printf("%d%d\n",p,u);
}
int deep[maxn],f[maxn][],log[maxn];
void build(int u){
for(int i=;i<=log[ deep[u] ];i++)
f[u][i]=f[f[u][i-]][i-];
for(int i=;i<=;i++){
if(to[u][i]){
deep[ to[u][i] ]=deep[u]+;
f[ to[u][i] ][]=u; build(to[u][i]);
}
}
}
inline void LCA_init(){
for(int i=;i<=maxdeep;i++)log[i]=log[i>>]+;
deep[]=;//??非常关键的地方，以谁为根谁的深度就是1
build();
}
inline int LCA(int x,int y){
if(deep[x]<deep[y])swap(x,y);
for(int i=log[deep[x]];i>=;i--){
if(deep[y]<=deep[f[x][i]])x=f[x][i];
}
if(x==y)return x;
for(int i=log[deep[x]];i>=;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];y=f[y][i];
}
}
return f[x][];
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",ch+);
insert(i);
}
scanf("%d",&m);
LCA_init();
for(int i=,a,b;i<=m;i++){
scanf("%d%d",&a,&b);
printf("%d\n",deep[LCA(vis[a],vis[b])]-);
}
return ;
}
/*问题描述
给出一些串，多组询问求两个串的最长公共前缀。字符串总长 < 10^6。
输入格式
第一行一个整数n，表示字符串的个数。
接下来n行，每行一个字符串（字符串不含空格）。
第n+2行一个整数m，表示询问总数。
接下来m行，每行两个整数a,b,表示询问第a个字符串和第b个字符串的最长公共前缀的长度。
输出格式
输出共m行，对于每个询问输出最长的公共前缀的长度
输入样例
5
abcdef
abcd
acd
cade
abcdef
4
1 2
2 3
1 5
3 4
输出样例
4
1
6
0
限制与约定
1<= m < 10^6
时间限制：1s
空间限制：256MB*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=1e6+;
char ch[maxn];
int n,m,to[maxn][],cnt,vis[maxn],maxdeep;
//vis[i]表示字符串i在trie树中位置
inline void insert(int p){
int u=;int len=strlen(ch+);
maxdeep+=len;
for(int i=;i<=len;i++){
int v=ch[i]-'a';
if(!to[u][v])to[u][v]=++cnt;
u=to[u][v];
}
vis[p]=u;
//printf("%d%d\n",p,u);
}
int deep[maxn],f[maxn][],log[maxn];
void build(int u){
for(int i=;i<=log[ deep[u] ];i++)
f[u][i]=f[f[u][i-]][i-];
for(int i=;i<=;i++){
if(to[u][i]){
deep[ to[u][i] ]=deep[u]+;
f[ to[u][i] ][]=u; build(to[u][i]);
}
}
}
inline void LCA_init(){
for(int i=;i<=maxdeep;i++)log[i]=log[i>>]+;
deep[]=;//??非常关键的地方，以谁为根谁的深度就是1
build();
}
inline int LCA(int x,int y){
if(deep[x]<deep[y])swap(x,y);
for(int i=log[deep[x]];i>=;i--){
if(deep[y]<=deep[f[x][i]])x=f[x][i];
}
if(x==y)return x;
for(int i=log[deep[x]];i>=;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];y=f[y][i];
}
}
return f[x][];
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",ch+);
insert(i);
}
scanf("%d",&m);
LCA_init();
for(int i=,a,b;i<=m;i++){
scanf("%d%d",&a,&b);
printf("%d\n",deep[LCA(vis[a],vis[b])]-);
}
return ;
}
用于优化dp：
/*问题描述
给出一个由S个不同的单词组成的字典和一个长字符串。把这个字符串分解成若干个单词的连接（单词可以重复使用），有多少种方法？
输入格式
输入包含多组数据。每组数据第一行为小写字母组成的待分解字符串，长度L不超过300 000，紧接着是单词个数S（1<=S<=4000）。第二行为S个单词，单词中间用空格隔开
S个单词由不超过100个小写字母组成。输入结束标志为文件结束符（EOF）。
输出格式
对于每组输出数据，输出分解方案数除以20071027的余数。
样例输入
abcd 4
a b cd ab
样例输出
Case 1: 2
样例解释：
方案1：abcd=a+b+cd; 方案二：abcd=ab+cd。
限制与约定
时间限制：1s
空间限制：128MB*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &a){
a=;bool b=;char x=getchar();
while(x<''||''<x){
if(x=='-')b=;
x=getchar();
}
while(''<=x&&x<=''){
a=(a<<)+(a<<)+x-'';
x=getchar();
}
if(b)a=-a;
}
char C[];
int temp;
template<typename T>
inline void write(T a){
if(a<){
putchar('-');
a=-a;
}
do{
C[++temp]=a%+'';
a/=;
}while(a);
while(temp)putchar(C[temp--]);
}
const int maxn=4e5+;
const int P=;
int to[maxn][],cnt,f[maxn];
char target[maxn],a[maxn];
bool vis[maxn];
inline void insert(){
int u=;
for(int i=strlen(a+);i;i--){//注意倒序插入
int v=a[i]-'a';
if(!to[u][v])to[u][v]=++cnt;
u=to[u][v];
}
vis[u]=;
}
inline void query(int p){
//printf("%d:",p);
int u=;
for(int i=;i<=;i++){//找位置p及之前的99位
if(p==i)break;
int v=target[p-i]-'a';
if(!to[u][v])break; //printf("v%d ",v); u=to[u][v];
if(vis[u])f[p]=(f[p]+f[p-i-])%P;
}
//printf("\n");
}
int s;
inline void clear(){
memset(to,,sizeof(to));
cnt=;
memset(f,,sizeof(f));
memset(vis,,sizeof(vis));
}
int main(){
int tt=;
while(scanf("%s",target+)!=EOF){
tt++;
clear(); scanf("%d",&s);
while(s--){
scanf("%s",a+);
insert();
}
int len=strlen(target+);
f[]=;
for(int i=;i<=len;i++)query(i);
printf("Case %d: %d\n",tt,f[len]);
}
return ;
}
问题描述
给定 一个含N个元素的数组A，下标从1开始，请找出下面式子的最大值： (A[L1]^ A[L1+1]^…^ A[R1])+ (A[L2]^ A[L2+1]^…^ A[R2])。其中1<= L1<= R1< L2<= R2<=N。式子中x^y表示x和y的按位异或运算。
输入格式
输入数据的第一行包含一个整数N，表示数组中的元素个数。 第二行包含N个整数A1,A2,…,AN。
输出格式
输出一行包含给定表达式可能的最大值。
输入样例
5
1 2 3 1 2输出样例
6限制与约定
满足条件的(l1,r1,l2,r2)有：(1,2,3,3)，(1,2,4,5)，(3,3,4,5)。
对于100%的数据，2 ≤ N ≤ 4*10^5，0 ≤ Ai ≤ 10^9。
时间限制：1s
空间限制：256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
template<typename T>
inline void read(T &a){
a=;bool b=;char x=getchar();
while(x<''||''<x){
if(x=='-')b=;
x=getchar();
}
while(''<=x&&x<=''){
a=(a<<)+(a<<)+x-'';
x=getchar();
}
if(b)a=-a;
}
char C[];
int temp;
template<typename T>
inline void write(T a){
if(a<){
putchar('-');
a=-a;
}
do{
C[++temp]=a%+'';
a/=;
}while(a);
while(temp)putchar(C[temp--]);
}
/*
main thought:预处理出prexor[i]表示位置a[1]^……^a[i]的xor值,
以及premax[i]表示max(prexor[j]~prexor[k]),由于递增，O(n)求出
最后扫描一遍即可
*/
const int maxn=4e5+;
int to[maxn*][],cnt;//空间别算错，二叉树
inline void insert(int num){
int u=;
for(int i=;i>=;i--){//倒序插入,32~0位
bool v=num&(<<i);//取出
if(!to[u][v])to[u][v]=++cnt;
u=to[u][v];
}
}
inline int query(int num){
int ans=,u=;
for(int i=;i>=;i--){
bool v=num&(<<i);//取出该位&
if(to[u][v^]){
u=to[u][v^];
ans=(ans<<|);
}
else {
u=to[u][v];
ans<<=;
}
}
return ans;
}
int prexor[maxn],maxpre[maxn],n,a[maxn],ans,now;
inline void clear(){
memset(to,,sizeof(to));
cnt=;
}
int main(){
read(n);
insert();//记得插入0
for(int i=;i<=n;i++){
read(a[i]);
prexor[i]=prexor[i-]^a[i];
insert(prexor[i]);
maxpre[i]=max(maxpre[i-],query(prexor[i]));
}
clear();
insert();//记得插入0
for(int i=n;i;i--){
now^=a[i];
insert(now);
ans=max(ans,maxpre[i-]+query(now));
}
write(ans);
return ;
}