今天复习字符巛 还剩下一点时间 我先 打一下模板
$ 1$ 最小表示法
贪心 首先把 $ S $ 复制一遍成一个环
然后定义两个指针 i j 从 i j 开始一次扩展 字符巛 的长度 即 从$0$ 的长度开始扩展到 $n-1$ ($k $最大到 $n$ >- 停止循环 找到答案)
然后比较其中是否相等
如果不相等就跳过循环
判断 当前 $S[i+k]$ 与$S[j+k]$ 的 大小 因为中间的字符串 都相等 所以 指针可以跳到 $x+k+1$ 处 $[x|i,j]$
然后因为 最小的指针一定不会移动到最大的指针的后面所以 答案为 $min(i,j)$
$ i,j $只循环到 n 的位置 因为以后都是一样的 了
code;
int i=1,j=2; int k=0; while(i<=n&&j<=n) { for(int k=0;k<n;k++) { if(S[i+k]!=S[j+k]) break; } if(k==n) break; if(s[i+k]>s[j+k]) i=i+k+1; else { if(s[i+k]<s[j+k]) j=j+k+1; } if(i==j) j++; } cout<<min(i,j);
2 .01 字典树
作用 ： 寻找异或最大值
方法 ：
插入： 每位每位地找 没有就扩展 扩展完之后 就插入
code:
void inset(int v) { int u=0; for(int i=32;i>=0;i--) { int k=(sum[v]>>i)&1; if(!ch[u][k]) { ch[u][k]=tot++; } u=ch[u][k]; } val[u]=sum[v]; }
寻找：从最高位 开始 搜寻 先找 不同的 后找相同的 注意 先插入 $sum[0]$ 保证有解
如果 找不到 就一定没有
code:
int find(int v) { int u=0; for(int i=32;i>=0;i--) { int k=(v>>i)&1; if(ch[u][k^1]) u=ch[u][k^1]; else u=ch[u][k]; } return val[u]; }
原文：https://www.cnblogs.com/OIEREDSION/p/11338801.html