专题总结（字符串）

字符串

前置声明

• 内容空着的板块，和标$?????????$的地方，笔者会慢慢地补全。
• $Bug$:最小循环表示法、$kmp$、$exkmp$

前缀表达式和后缀表达式

对于直接求中缀表达式的值：

• 维护一个数字栈和一个运算符栈
• 若当前字符为数字，直接插入栈（或融入栈顶）;
  若当前字符为运算符，且比栈顶运算优先级高（不能相等），直接插入;
  否则弹出栈顶，取数字栈顶两个数进行运算，再把结果塞回数字栈，直到满足条件为止。
• 若当前字符为左括号，直接插入;若为右括号，弹栈顶直到遇到左括号。

如果加上了未知数，就把数字栈变为多项式栈，用结构体储存所有项的系数，模拟一般多项式运算即可。

看一道考试题化简。

字符串的最小循环表示法

该问题实质是求$S$串的一个位置，从这个位置开始循环输出（输完）$S$，得到的$S'$字典序最小。
首先，这字符串在题目中有点像环一样被处理，可以复制一遍（破环为链）方便处理。
我们只能比较形成的字符串，于是我们要枚两个位置。
很容易想出一个$O(n^2)$暴力：(强制$i<j$）

re int i=1,j=2;
while(j<=n)
{
  if(s[i]>s[j]) i=j,j=i+1;
  if(s[i]<s[j]) ++j;//除去不优的那个位置
  if(s[i]==s[j])
  {
    re int k=1;
    while(k<n) 
    {
      if(s[i+k]>s[j+k]) {i=j,j=i+1;break;}
      if(s[i+k]<s[j+k]) {++j;break;}
      ++k;
    }
  }
  return i;
}

但这样$i$移动太慢了。
当$s[i+k]>s[j+k]$时，既然我们知道$i～i+k$不优，为什么不能直接把$i$跳到$i+k+1$再比较呢？
这样，复杂度可以优化到$O(n)$。

il int work()
{
  re int i=1,j=2,k=0;
  while(i<=n&&j<=n&&k<=n)
    {
      re int t=a[i+k]-a[j+k];
      if(!t) ++k;
      else
    {
      if(t>0) i+=k+1;
      if(t<0) j+=k+1;
      if(i==j) ++j;
      k=0;
    }
    }
  return min(i,j);
}
  return i;
}

注意在$i=i+k$后可能导致$i>=j$，需要把$j=i+1$。

$manacher$算法

该算法用于求字符串中最长回文串的长度。
解这个问题，最无脑的就是枚举两端点扫中间判，复杂度$O(n^3)$。
稍微优化一些，就是枚举回文串正中间那个地方（要讨论是点还是点中间），然后同时向两边拓展，复杂度$O(n^2)$。
但该“聪明的暴力”还是有很多不足：

• 需要分类讨论

$manacher$算法一开始就在每两个字符中间及字符串两端插入另一字符'#'。
这样就不用讨论了，直接枚每个字符作为正中间即可。

• 会出现很多子串被重复多次访问，时间效率大幅降低。

用一个辅助数组$r$表示每个点能够拓展出的回文串长度。
我们先设置一个辅助变量$mr$，表示已经触及到的最右边的字符;一个辅助变量$mid$，表示包含$mr$的回文串的对称轴所在的位置。
从$s[1]$遍历到$s[len]$,
当$mid<i<mr$：
设$i$关于$mid$的对称点为$j$，显然$r[i]$一定不会小于$r[j]$。（对称）
而$j$可以通过$(mid<<1)−i$算出。
那么我们就设置$r[i]=r[j]$，(优化：$r[i]$的拓展就少走了$r[j]$步）然后接着尝试扩展，这样就可以较快地求出$r[i]$，然后更新$mr$和$mid$。
当$i$在$mr$右边时，我们无法得知关于$r[i]$的信息，只好从$1$开始遍历，然后更新$mr$和$mid$。

int main()
{
    scanf("%s",s+1);n=strlen(s+1);
  s[0]='*';s[n<<1|1]='#';
    fq(i,n,1) s[i<<1]=s[i],s[(i<<1)-1]='#';
    fp(i,1,n<<1)
    {
        p[i]=mx>i?min(p[2*id-i],mx-i):1;
        while(s[i-p[i]]==s[i+p[i]]) ++p[i];
        if(i+p[i]>mx) mx=i+p[i],id=i;
        ans=max(ans,p[i]-1);
    }
    printf("%d\n",ans);
    return 0;
}

$kmp$算法

$KMP$算法主要是用来减少失配后，不利用已知信息而造成的 进行无意义匹配 的次数。
搞不清可以看看$SYC$的动图。SYC博客

所以，整个$KMP$的重点就在于当某一个字符与主串不匹配时，我们应该知道$j$指针要移动到哪？

我们可以试一试。

• $S=\{abacbcd\}$
  $T=\{abad\}$

如上，可以发现第$4$位失配。鉴于$S[3]=S[1]=T[1]$，我们最好从$T$串第$2$位开始匹配。

• $S=\{abcabcd\}$
  $T=\{abcabb\}$

如上，可以发现第$6$位失配。鉴于$S[4]=T[4]=T[1],S[5]=T[5]=T[2]$，我们最好从$T$串第$3$位开始匹配。

则可注意到，当匹配失败时，$j$下一次最优开始匹配的位置 的前一个 $k$，存在着这样的性质：最前面的$k$个字符和$j$之前的最后$k$个字符是一样的，即$j$前面字符串的满足 前缀后缀相同 的长度。
存这个值的数组被命名为$next$数组。

然后怎么求这玩意儿？
方法是$T$串自己匹配自己。
我们从$2$往后一一求出每个位置的$next$。

求出$next$后，好好利用就可以了。剩下就是模拟。
复杂度$O(|S|+|T|)$

int main()
{
  scanf("%s%s",s+1,t+1);
  n=strlen(s+1);m=strlen(t+1);
  re int j=0;
  nxt[1]=0;
  fp(i,2,m)
    {
      while(j&&t[i]!=t[j+1]) j=nxt[j];
      if(t[i]==t[j+1]) ++j;
      nxt[i]=j;
    }
  j=0;
  fp(i,1,n)
    {
      while(j&&s[i]!=t[j+1]) j=nxt[j];
      if(s[i]==t[j+1]) ++j;
      if(j==m) {printf("%d\n",i-m+1);j=nxt[j];}
    }
  fp(i,1,m) printf("%d ",nxt[i]);puts("");
  return 0;
}

$exKMP$算法

该算法用于求$T$串与$S$串每一个后缀的最长公共前缀，是$KMP$算法和$manacher$算法相结合的产物。
继续使用$manacher$算法中的变量$mr$,$mid$。

$Trie$树

看个图就知道这是什么玩意儿了。示意图
本质上是利用公共前缀减少存储空间。
用途：

• 查找一字符串是否存在
• 给所有字符串排序
• 计算两字符串最长公共前缀（$LCP$）长度
• 与异或运算有关（详见某道求异或最大值的题）

给一个不用递归的模板

il void Modify(re int x)
{
  re int u=1;
  fq(d,30,0)
    {
      re int w=((x>>d)&1);
      if(!t[w][u]) t[w][u]=++tot;
      u=t[w][u];
    }
}
il int Query(re int x)
{
  re int u=1,s=0;
  fq(d,30,0)
    {
      re int w=((x>>d)&1);
      if(t[!w][u]) s+=(1<<d),u=t[!w][u];else u=t[w][u];
    }
  return s;
}

$AC$自动机

首先用所有的匹配串构建一颗$Tire$树。
然后，像$kmp$中的$next$数组一样，为减少重复检查次数，建立失配指针。
构建原则是

• 第二层所有结点的失配指针都要指向根节点
• 从当前节点开始，沿着其父节点的失配指针不断向上跑，直到到达一个节点，它的儿子中有当前结点的字母，然后把这两个一样的字母连起来。

这样（还是很像$kmp$），每次失配后就跳转到失配指针,继续没配完部分的匹配。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define il inline
#define re register
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+5;
int n,cnt;
string s[N];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
struct Tree
{
  int fail,vis[26],end;
}AC[N];
struct res
{
  int num,pos;
  bool operator < (const res &x)
  {
    if(num==x.num) return pos<x.pos;
    return num>x.num;
  }
}Ans[N];
il void Upd(re int x)
{
  memset(AC[x].vis,0,sizeof(AC[x].vis));
  AC[x].fail=0;AC[x].end=0;
}
il void Build(re string s,re int num)
{
  re int l=s.length(),now=0;
  fp(i,0,l-1)
    {
      if(!AC[now].vis[s[i]-'a']) AC[now].vis[s[i]-'a']=++cnt,Upd(cnt);
      now=AC[now].vis[s[i]-'a'];
    }
  AC[now].end=num;
}
il void Get_fail()
{
  queue<int>Q;
  fp(i,0,25)
    if(AC[0].vis[i]) AC[AC[0].vis[i]].fail=0,Q.push(AC[0].vis[i]);
  while(!Q.empty())
    {
      re int u=Q.front();Q.pop();
      fp(i,0,25)
    if(AC[u].vis[i]) AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i],Q.push(AC[u].vis[i]);
    else AC[u].vis[i]=AC[AC[u].fail].vis[i];
    }
}
il int Query(re string s)
{
  re int l=s.length(),now=0,ans=0;
  fp(i,0,l-1)
    {
      now=AC[now].vis[s[i]-'a'];
      for(re int t=now;t;t=AC[t].fail) ++Ans[AC[t].end].num;
    }
  return ans;
}
int main()
{
  ios::sync_with_stdio(false);
  while(1)
    {
      cin>>n;if(!n) break;
      cnt=0;Upd(0);
      fp(i,1,n)
    {
      cin>>s[i];Ans[i].num=0,Ans[i].pos=i;
      Build(s[i],i);
    }
      AC[0].fail=0;
      Get_fail();
      cin>>s[0];
      Query(s[0]);
      sort(&Ans[1],&Ans[n+1]);
      cout<<Ans[1].num<<endl;
      cout<<s[Ans[1].pos]<<endl;
      fp(i,2,n)
      if(Ans[i].num==Ans[i-1].num) cout<<s[Ans[i].pos]<<endl;
      else break;
    }
}

字符串哈希

详见专项总结从map到hash。