浅谈字符串算法

本文主要是介绍浅谈字符串算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Luogu P3805 manacher算法

马拉车算法是求最长回文串的算法，其核心在于减少了冗余的重复计算，利用当前已知的数据尽可能的推出之后的数据，从而达到线性的复杂度。

我认为这个算法的核心之处是充分利用了回文串的对称性。

首先是处理回文串的一个小技巧，对于奇偶回文串，我们只需要在相邻的两个字符之间加上一个 '#' 字符，那么无论是奇串还是偶串，都会变成奇串（自行模拟）。

对于你目前已经求出的回文串 \([1,mx]\)，定义 \(mid\) 为这个串的回文中心，p[i] 数组表示以 \(i\) 为回文中心的最长的回文半径。

首先给出一个结论，以 \(i\) 为回文中心的字符串的最长回文串的长度会等于 p[i]-1，因为要减去一个 '#'。

那么怎么进行 \(manacher\) 呢？

对于一个 \(i(mid<i<mx)\)，这时根据对称性，\(i\) 的对称点 \(i'\) 点为 \(mid*2-i\)，那么以 \(i\) 为回文中心的最长回文半径一定不会小于以 \(i'\) 点为回文中心的最长回文半径，所以我们可以先让 p[i]=min(p[mid*2-i],mx-i)（注意，回文半径的长度不能超过 \(mx-i\)），然后在暴力一个一个判断出 \(i\) 超过 \(mx\) 范围的回文串，并且更新 \(mx\) 和 \(mid\)，反复如此，终可求矣。

如果 \(i(mx<i)\) 呢？就直接考虑暴力求了，然后再更新 \(mx\) 和 \(mid\)。

#include<bits/stdc++.h>
using namespace std;
const int N=3e7+5;
int cnt,p[N],ans;
char s[N];
void read(char *str){
  char ch=getchar();
  str[0]='@';
  while(ch>='a'&&ch<='z') str[++cnt]='#',str[++cnt]=ch,ch=getchar();
  str[++cnt]='#';
}
int main(){
  read(s);
  int mid=1,mx=1;
  for(int i=1;i<cnt;i++){
    if(i<mx){
      p[i]=min(p[(mid<<1)-i],mx-i);
    }
    else p[i]=1;
    while(s[i-p[i]]==s[i+p[i]]) p[i]++;
    if(mx<i+p[i]){
      mx=i+p[i];
      mid=i;
    }
    ans=max(ans,p[i]-1);
  }
  printf("%d",ans);
  return 0;
}

Luogu P1368 最小表示法

最小表示法就是对于一个字符串，求她的循环同构的字符串的最小的那个。

如字符串 "gfedcba"，她的循环同构的字符串为：

"agfedcb"，"bagfedc"，"cbagfed"，"dcbagfe"，"edcbagf"，"fedcbag"

那么很显然，对于她来说，她的最小表示法为 "agfedcb"。

考虑怎么来求一个字符串的最小表示法

注：这里存字符串从 \(0\) 开始存。

我们定义两个指针 \(i\) 和 \(j\)，分别指向字符串 \(s\) 中的两个不同的位置（指向位置相同时就无意义了），定义当前分别从 \(i\)，\(j\) 开始已经匹配了 \(k\) 个字符（从 \(i\) ，\(j\) 开始，包括 \(i\)，\(j\) 本身的后 \(k\) 个字符相等）。

那么对于 s[(i+k)%n] 和 s[(j+k)%n]：

• 如果相等那么匹配数 k++；

• 如果 s[(i+k)%n]>s[(j+k)%n]，则说明 \(i\sim i+k\) 之间的字符都不会作为最小表示法的开头，所以 \(i\) 直接跳到 \(i+k+1\)；

• 如果 s[(i+k)%n]<s[(j+k)%n]，同理可得 \(j\) 跳到 \(j+k+1\)。

最后，\(i\) 和 \(j\) 位置最小的点就是最小表示法的开头点，记为 \(ans\)。最后输出 s[(i+ans)%n] 就好了。

有一点要注意的，就是 \(i\) 不能等于 \(j\)，因为要指向不同的位置，否则将会一直匹配，所以相等时让 i++ 就好了。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
  int ans=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}
  while(isdigit(ch)){ans=(ans<<3)+(ans<<1)+ch-48;ch=getchar();}
  return ans*f;
}
const int N=3e5+5;
int n,ans;
int s1[N];
int minshow(){
  int i=0,j=1,k=0;
  while(i<n&&j<n&&k<n){
    if(s1[(i+k)%n]==s1[(j+k)%n]) k++;
    else{
      if(s1[(i+k)%n]>s1[(j+k)%n]) i+=k+1;
      else j+=k+1;
      if(i==j) i++;
      k=0;
    }
  }
  return min(i,j);
}
int main(){
  n=read();
  for(int i=0;i<n;i++){
    s1[i]=read();
  }
  ans=minshow();
  for(int i=0;i<n;i++){
    printf("%d ",s1[(i+ans)%n]);
  }
  return 0;
}

Luogu P3375 KMP字符串匹配

激动人心的 看毛片 算法来了

KMP算法核心处也是减少重复冗余的计算。

朴素算法就是双指针一个一个匹配，当有一个失配后，就将模式串从头开始匹配。复杂度可以被卡到 \(O (nm)\)

KMP失配后不是从头开始，而是利用一个 kmp[j] 数组，记录 \(j+1\) 失配后 \(j\) 应该从哪里开始重新匹配 。并且很容易发现，文本串的指针只增不减，模式串的指针会减少也会增加（因为每次失配后只用改变模式串指针位置就好了）。

上图：

此时 a[i]!=b[j+1] 失配。

于是我们将 \(j\) 从 \(4\) 移动到 \(2\) 的位置，重新开始匹配，就避免了从头开始匹配。

我们先假设我们已经求出了 kmp 数组，那么对于这个问题就很简单了。

我们只用双指针依次匹配，当失配后令模式串指针 j=kmp[j] ，再与文本串重新匹配。

代码如下：

j=0;
  for(int i=1;i<=lena;i++){
    while(j&&a[i]!=b[j+1]) j=kmp[j];//如果不匹配，模式串就往前跳
    if(a[i]==b[j+1]) j++;//如果相等就匹配下一位
    if(j==lenb){//找到相同的串后输出起始位置
      printf("%d\n",i-lenb+1);
      j=kmp[j];//跳回去
    }
  }

因为要让指针跳回的尽可能少，所以我们就要让 kmp[j] 数组存的可以跳回的点尽可能大，所以我们就可以让 kmp[j] 数组为从 \(1 \sim j-1\) 位中，前缀和后缀相等的部分的最长长度是多少。这样就可以让指针每次跳回的尽可以少。

那么怎么求出 kmp[j] 数组呢？

其实就是用模式串对模式串自己做KMP操作

引用 Matrix67 Blog 中的巧妙证明就是

代码如下：

j=0;
  for(int i=2;i<=lenb;i++){
    while(j&&b[i]!=b[j+1]) j=kmp[j];
    if(b[i]==b[j+1]) j++;
    kmp[i]=j;
  }

复杂度如何证明？

引用 \(rqy\) 大佬的证明

每次位置指针 \(i++\) 时，失配指针 \(j\) 至多增加一次，所以 \(j\) 至多增加 \(len\) 次，从而至多减少 \(len\) 次，所以就是 \(\Theta(len_N + len_M) = \Theta(N + M)\) 的。

至此，我们结束了看毛片算法

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char a[N],b[N];
int lena,lenb;
int kmp[N],j;
int main(){
  cin>>a+1;
  cin>>b+1;
  lena=strlen(a+1),lenb=strlen(b+1);
  j=0;
  for(int i=2;i<=lenb;i++){
    while(j&&b[i]!=b[j+1]) j=kmp[j];
    if(b[i]==b[j+1]) j++;
    kmp[i]=j;
  }
  j=0;
  for(int i=1;i<=lena;i++){
    while(j&&a[i]!=b[j+1]) j=kmp[j];
    if(a[i]==b[j+1]) j++;
    if(j==lenb){
      printf("%d\n",i-lenb+1);
      j=kmp[j];
    }
  }
  for(int i=1;i<=lenb;i++) printf("%d ",kmp[i]);
  return 0;
}

Luogu P3808 AC自动机（简单版）

AC自动机，全称"Aho_Corasick_Automaton"，用于求解多个模式串匹配一个文本串的问题。联想到之前的学过的算法，发现有一个KMP算法（看毛片）可以求解一个模式串匹配一个文本串的问题，那么利用OI的基本思想之一的 x套x 思想，是不是可以考虑把两个算法结合起来，以达到一种神奇的效果呢？

我们发现，对于多个模式串，我们可以建一棵 \(trie\) 树方便求出他们的公共前缀，然后就可以在 \(trie\) 树上面看毛片KMP了！

众所周知，KMP最重要的是失配数组 fail，那我们怎么在 \(trie\) 树上求 fail 数组呢？

很简单，只用跑一边 \(bfs\) 就好了，逻辑很明了看看代码就会了，不再赘述。注意优化！

void build(){
  for(int i=0;i<26;i++) if(trie[0][i]) fail[trie[0][i]]=0,q.push(trie[0][i]);
  while(!q.empty()){
    int u=q.front();q.pop();
    for(int i=0;i<26;i++){
      if(trie[u][i]) fail[trie[u][i]]=trie[fail[u]][i],q.push(trie[u][i]);
      else trie[u][i]=trie[fail[u]][i];//优化，没有这条边的时候早晚要跳回去，还不如现在跳
    }
  }
}

有了 \(fail\) 数组，那么怎么匹配呢？

也很简单，我们只用遍历，枚举一条当前文本串字符连向的边，然后把这些点的 \(fail\) 全部跑一边，然后答案直接加上结束标记 \(end\)。注意不要重复计算，用完的标记要丢掉！

int query(char *str){
  int len=strlen(str),p=0,res=0;
  for(int i=0;i<len;i++){
    p=trie[p][str[i]-'a'];
    for(int t=p;t&&end[t]!=-1;t=fail[t]) res+=end[t],end[t]=-1;
  }
  return res;
}

最后，注意常数优化，这题别用蓝书上面的代码，一直卡常，吸氧吸中毒了都没用。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n;
int trie[N][26],end[N],fail[N],tot;
queue<int> q;
void ins(char *str){
  int len=strlen(str),p=0;
  for(int i=0;i<len;i++){
    int ch=str[i]-'a';
    if(!trie[p][ch]) trie[p][ch]=++tot;
    p=trie[p][ch];
  }
  end[p]++;
}
void build(){
  for(int i=0;i<26;i++) if(trie[0][i]) fail[trie[0][i]]=0,q.push(trie[0][i]);
  while(!q.empty()){
    int u=q.front();q.pop();
    for(int i=0;i<26;i++){
      if(trie[u][i]) fail[trie[u][i]]=trie[fail[u]][i],q.push(trie[u][i]);
      else trie[u][i]=trie[fail[u]][i];
    }
  }
}
int query(char *str){
  int len=strlen(str),p=0,res=0;
  for(int i=0;i<len;i++){
    p=trie[p][str[i]-'a'];
    for(int t=p;t&&end[t]!=-1;t=fail[t]) res+=end[t],end[t]=-1;
  }
  return res;
}
char tmp[N];
int main(){
  cin>>n;
  for(int i=1;i<=n;i++) cin>>tmp,ins(tmp);
  build();
  cin>>tmp;
  printf("%d",query(tmp));
  return 0;
}

Luogu P5410 扩展KMP（Z函数）

扩展看毛片。

其实我觉得有点像马拉车思想和KMP的结合，但这三个算法都是利用减少冗余重复计算来达到线性的。

相较于KMP算法，exKMP算法求的是模式串与文本串的后缀的LCP（最长公共前缀）

我们令 extend 数组为文本串 \(S\) 的后缀与模式串 \(T\) 的LCP，z 数组为模式串 \(T\) 的后缀与模式串 \(T\) 的LCP。

怎么来求呢？先画图。

我们假设当前已经求出了 \(1 \sim i\) 的 extend 数组和 z 数组，在匹配过程中记最远的匹配距离为 \(r\)，即 \(r=max(i+extend[i]-1)\)，能够取到最大值 \(r\) 的 \(i\) 我们记为 \(l\)。

• 第一种情况，当 \(i+L\) 在 \(r\) 左边时：

z[i-l+1] 代表着 \(T[i-l+2\sim m]\) 中与 \(T[1 \sim m]\) 的最长公共前缀，我们设为 \(L\)。

所以 \(T[1\sim L]=T[i-l+2\sim i-l+2+L]\)，图中蓝色与绿色部分长度字符都相等（下文简称“相等”）。

根据 \(l\) 和 \(r\) 的定义，可知 \(S[l\sim r]=T[1\sim r-l+1]\)，所以 \(S[i+1\sim i+L]=T[i-l+2\sim i-l+2+L]\)，图中红色与蓝色部分相等。

综上图中红绿蓝三个部分都相等

因为 \(S[i\sim n]\) 与 \(T[1\sim m]\) 的最长公共前缀为 extend[i]，所以 extend[i]=L。

• 第二种情况，当 \(i+L\) 在 \(r\) 右边时：

我们令 extend[i]=r-i+1 靠暴力跑出剩下的答案。

那么从哪里开始跑暴力呢？

就从当前的 \(i\) 开始跑，与模式串一一比对。

最后别忘了更新一下 \(l\) 和 \(r\)。

对于 \(z\) 数组就是重复一遍这个算法的事情了。

因为每个点最多跑一次，所以做一遍的复杂度是线性的。

对 z 和 extend 分别做了一遍，所以总的时间复杂度为\(\Theta(n+m)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e7+5;
char s[N],t[N];
int lens,lent;
int z[N],extend[N];
void doZ(){
  z[1]=lent;
  for(int i=2,l=0,r=0;i<=lent;i++){
    if(i<=r) z[i]=min(z[i-l+1],r-i+1);
    while(i+z[i]<=lent&&t[i+z[i]]==t[z[i]+1]) ++z[i];
    if(i+z[i]-1>r) l=i,r=i+z[i]-1;
  }
}
void exkmp(){
  doZ();
  for(int i=1,l=0,r=0;i<=lens;i++){
    if(i<=r) extend[i]=min(z[i-l+1],r-i+1);
    while(i+extend[i]<=lens&&s[i+extend[i]]==t[extend[i]+1]) ++extend[i];
    if(i+extend[i]-1>r) l=i,r=i+extend[i]-1;
  }
}
int main(){
  scanf("%s%s",s+1,t+1);
  lens=strlen(s+1);lent=strlen(t+1);
  exkmp();
  long long ans1=0,ans2=0;
  for(int i=1;i<=lent;i++) ans1^=1ll*i*(z[i]+1);
  for(int i=1;i<=lens;i++) ans2^=1ll*i*(extend[i]+1);
  printf("%lld\n%lld",ans1,ans2);
  return 0;
}

还有一点就是为什么跑暴力不分情况，写在循环外面，因为对于上述的情况一，不可能有 \(T[L+1]=S[i+L+1]\) 了。因为如果存在 \(T[L+1]=S[i+L+1]\)，他们的最长公共前缀就是 \(L+1\) 了，\(L\) 就不是最长公共前缀了，就不满足 \(L\) 的定义了。所以只会在情况二的时候跑暴力，这也是算法的巧妙精简美啊！

这篇关于浅谈字符串算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！