今天复习字符巛 还剩下一点时间  我先 打一下模板

$ 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
     
      s[j+k]) i=i+k+1;       else　　　　{　　　　　　if(s[i+k]
     

 

 

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];}

 

 

$3$ 状态很差,但是还是坚持来写下博客啦

KMP

作用 匹配或者最长字串

首先 fail数组 记的是 前i位 的最长前缀和后缀 

求fail 数组首先得与自己比对  注意得从第二位开始 求出回退值

code:

fail[0]=-1;        int j=-1;        for(int i=1;i
     
      -1&&(s[1][j+1]!=s[1][i])) j=fail[j];                        if(s[1][j+1]==s[1][i]) j++;            fail[i]=j;        }
     

求匹配   匹配使得前后缀一样 就很强 从第一位开始

int j=-1;    int ans=0;    fail[0]=-1;    for(int i=0;i
     
      -1&&(s[1][j+1]!=s[v][i])) {            ans=max(ans,j);        j=fail[j];}                if(s[1][j+1]==s[v][i]) j++;　　　　　if(j==m) 　　　　　{
    　　　　　
     

　　　　　　　　ans=max(j+1,ans); 　　　　　}     }    return ans;

$@$求最长公共字串匹配

找一个串 然后挨个匹配 找最小值 然后删除第一个元素 再次找最小值 最后取max 

介绍一下动态数组的erase神操作

 

#include
     
      using namespace std;int n;string  s[8];int fail[3000];int  kmp(int v){    int j=-1;    int ans=0;    fail[0]=-1;    for(int i=0;i
      
       -1&&(s[1][j+1]!=s[v][i])) {            ans=max(ans,j);        j=fail[j];}                if(s[1][j+1]==s[v][i]) j++;            ans=max(ans,j+1);    }    return ans;}int main(){    cin>>n;    for(int i=1;i<=n;i++)    {        cin>>s[i];    }    int aans=0;    while(s[1].size())    {    int ans=100000000;        fail[0]=-1;        int j=-1;        for(int i=1;i
       
        -1&&(s[1][j+1]!=s[1][i])) j=fail[j];                        if(s[1][j+1]==s[1][i]) j++;            fail[i]=j;        }    for(int i=2;i<=n;i++)    {                ans=min(ans,kmp(i));            }       aans=max(aans,ans);       s[1].erase(s[1].begin());    }    cout<
       
      
     

  

 

$@@$结论 字符串乘方 i%(i-fail[i])==0 那么一定有乘方 个数为$i/(i-fail[i])$

 $4$马拉车

首先初始化 把回文串都变成奇数回文串

类似于这样

void init(){    S[0]='#';    S[1]='#';    for(int i=0;i

 

一共由两种大情况 i 在已经更新的回文串maxlen 的右边或左边

对于i在左边的情况 $r[i] =min|{r[2*p-i],maxlen-i+1}|$ 其中$2*p-i$是$i$ 关于$p $对称的回文对应位置

对于i 在右边的情况 $r[i]=1$ 

　　　　　if(i

 

然后挨着扩展

类似于这样

while(S[i-r[i]]==S[i+r[i]])r[i]++;

最后更新maxlen 和p 的$val$

　　　　if(i+r[i]-1>maxlen)         {             maxlen=i+r[i]-1;             P=i;         }

 

注意到r数组位是最长回文半径（包括自己）

$r[i]-1$ 是原字符串的回文长度

　　　　　　　　　

string 类型可以直接比较  字典序

strcpy strcmp strlen 字符数组的函数