字符串进阶

计算机学院 21级 何丰辰

---

1. 扩展KMP（Z算法）

1.1 基础知识

• KMP

1.2 算法描述

我们需要处理从字符串 $s$ 中某一位出发，最多能匹配字符串 $p$ 中多少个字符

暴力做法：枚举所有位 $O(n)$，进行匹配 $O(m)$，总时间复杂度 $O(nm)$

优化：二分+哈希 $O(nlogm+m)$

扩展KMP：能以线性时间复杂度求出一个字符串 $s$ 和它的任意后缀 $s[i] \cdots s[n]$ 的最长公共前缀的长度

与KMP的区别：KMP是到 $s[i]$ 结束匹配，扩展KMP是从 $s[i]$ 开始匹配

1.3 具体分析

对于 $i>1$ 的位置 $i$，用 $z[i]$ 表示字符串 $s$ 和后缀 $s[i] \cdots s[n]$ 的最长公共前缀的长度

定义 $z[1]=0$，然后从 $2$ 到 $n$ 枚举 $i$，依次计算 $z[i]$ 的值

假设正在计算第 $i$ 个位置的值 $z[i]$，此时 $z[1] \cdots z[i-1]$ 都已经计算好了

则对于任意 $j\ (j<i)$，有 $s[j] \cdots s[j+z[j]-1] \ = \ s[1] \cdots s[z[j]]$

为了计算 $z[i]$，在枚举 $i$ 的过程中，我们需要维护一个 $R$ 最大的区间 $[L,R]$，其中

$\begin{cases}L=j& (j<i)\\R=j+z[j]-1& (j<i)\end{cases}$

初始时 $L=1,\ R=0$，即空区间

有如下几种情况：

1. 若 $i \leq R$，则根据定义有 $s[L] \cdots s[R]\ =\ s[1] \cdots s[R-L+1]$

   令 $k=i-L+1$，即 $i$ 在 $[L,R]$ 中的位置对应了 $k$ 在 $[1,R-L+1]$ 中的位置

   此时 $s[i] \cdots s[R]\ =\ s[k] \cdots s[R-L+1]$

   • 若 $z[k]<R-i+1$，说明从 $k$ 开始匹配不到 $R-L+1$ 那么远，也就是说从 $i$ 开始匹配不到 $R$ 那么远，此时 $z[i]=z[k]$
   • 若 $z[k] \ge R-i+1$，说明从 $k$ 开始可以匹配到 $R-L+1$ 那么远，也就是说从 $i$ 开始可以匹配到 $R$ 那么远，此时从 $R+1$ 开始继续暴力向后匹配即可，即令 $z[i]=R-i+1$ 并继续匹配

2. 若 $i>R$

   直接暴力枚举匹配即可

求出 $z[i]$ 后更新 $L$ 和 $R$

时间复杂度：暴力向后匹配的过程中 $R$ 的值也在同步增加，而 $R$ 最多只会被加 $O(n)$ 次，因此总复杂度为 $O(n)$

1.4 代码模板

vector<int> exkmp(string s){
    int n=(int)s.size();
    s="#"+s;
    vector<int> z(n+1);
    int L=1,R=0;
    for(int i=2;i<=n;i++){
        if(i>R)z[i]=0;
        else z[i]=min(z[i-L+1],R-i+1);
        while(i+z[i]<=n&&s[1+z[i]]==s[i+z[i]])z[i]++;
        if(i+z[i]-1>R)L=i,R=i+z[i]-1;
    }
    return z;
}

1.5 例题

1.5.1 （模板题）扩展 KMP（Z 函数）

题目描述：给定字符串 $s$ 和 $p$，求：$p$ 的 $z$ 数组、从字符串 $s$ 中每一位出发，最多能匹配字符串 $p$ 的字符数

题目分析：模板题

参考代码：

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=2e7+10;

ll z[2*N];

void exkmp(string s){
    int n=(int)s.size();
    s="#"+s;
    int L=1,R=0;
    for(int i=2;i<=n;i++){
        if(i>R)z[i]=0;
        else z[i]=min(z[i-L+1],1ll*R-i+1);
        while(i+z[i]<=n&&s[1+z[i]]==s[i+z[i]])z[i]++;
        if(i+z[i]-1>R)L=i,R=i+z[i]-1;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s,p;
    cin>>s>>p;
    int n=(int)s.size(),m=(int)p.size();
    exkmp(p+"#"+s);
    ll ans1=m+1,ans2=0;
    for(int i=2;i<=m;i++)ans1^=i*(z[i]+1);
    for(int i=m+2;i<=n+m+1;i++)ans2^=(i-m-1)*(z[i]+1);
    cout<<ans1<<"\n"<<ans2;
    return 0;
}

1.5.2 Password

题目描述：给定字符串 $s$，求出最长的子串 $p$，满足 $p$ 是 $s$ 的前缀、$p$ 是 $s$ 的后缀、$p$ 还以非前后缀的形式出现在 $s$ 中。$1 \leq |s| \leq {10}^6$

题目分析：对于某个位置 $i$，若 $z[i]=n-i+1$，则从 $i$ 到字符串结尾这一段既是前缀也是后缀，只需满足 $1$ 到 $i-1$ 中最大的 $z[]$ 大于等于 $z[i]$ 即满足 $p$ 还以非前后缀的形式出现在 $s$ 中

参考代码：

#include<bits/stdc++.h>
using namespace std;

vector<int> exkmp(string s){
    int n=(int)s.size();
    s="#"+s;
    vector<int> z(n+1);
    int L=1,R=0;
    for(int i=2;i<=n;i++){
        if(i>R)z[i]=0;
        else z[i]=min(z[i-L+1],R-i+1);
        while(i+z[i]<=n&&s[1+z[i]]==s[i+z[i]])z[i]++;
        if(i+z[i]-1>R)L=i,R=i+z[i]-1;
    }
    return z;
}

int main(){
    string s;
    cin>>s;
    int n=(int)s.size();
    vector<int> z=exkmp(s);
    vector<int> x(n+1);
    for(int i=1;i<=n;i++){
        x[i]=max(x[i-1],z[i]);
    }
    int pos=0;
    for(int i=n;i>=1;i--){
        if(z[i]==n-i+1&&x[i-1]>=z[i]){
            pos=i;
        }
    }
    s="#"+s;
    if(pos)cout<<s.substr(pos,n-pos+1);
    else cout<<"Just a legend";
    return 0;
}

---

2. Manacher

2.1 基础知识

• 回文串：若一个字符串从左向右读和从右向左读是一样的，则称为回文串
• 字符串长度：字符串中的字符数称为字符串的长度
• 回文串按长度的奇偶分为奇数长度的回文串和偶数长度的回文串
• 子串：一个字符串中连续的一段字符串
• 回文子串：是一个字符串的子串且是回文串

2.2 最长回文子串问题

2.2.1 描述

求给定字符串中最长的回文子串

2.2.2 暴力做法

枚举所有子串，分别检查是否是回文串

复杂度分析：

• 枚举子串：$O(n^2)$
• 检查是否是回文串：$O(n)$

总时间复杂度：$O(n^3)$

2.2.3 优化

容易发现，若一个字符串 $s$ 不是回文串，那么在 $s$ 两边加上同样长度的字符得到的字符串也不是回文串

因此考虑枚举回文串的中心位置，然后向两边扩展到最远位置

复杂度分析：

• 枚举中心位置：$O(n)$
• 向两边扩展：$O(n)$

总时间复杂度：$O(n^2)$

注意

枚举中心位置的时候要按照子串长度的奇偶分类讨论

2.2.4 其他做法

• 二分+哈希：$O(nlogn)$
• Manacher：$O(n)$

2.3 算法描述

Manacher，俗称“马拉车”，可以在线性时间复杂度内求出从字符串中任意位置出发，向两边最远能扩展出的回文子串的长度

2.4 小技巧

在正式介绍Manacher算法前，先学习一个小技巧：

对于字符串 $s$，用一个 $s$ 中不存在的字符（例如 $'\$'、'\#'$ 等）把 $s$ 中的字符隔开（开头和结尾也要加）

例：

• $aba$ 变为 $\$a\$b\$a\$$
• $cc$ 变为 $\$c\$c\$$

结论：已知新字符串的奇数长度的最长回文子串长度为 $len$，原字符串最长回文子串长度为 $\frac{len}{2}$

简单证明

设原串为 $s$，长度为 $n$，新串为 $t$，长度为 $m$，新串中奇数长度的最长回文子串长度为 $len$

已知 $t[i]=\begin{cases}插入的字符& \text{i为奇数}\\原串中的字符& \text{i为偶数}\end{cases}$

又因为 $\text{插入的字符}\neq\text{原串中的字符}$

所以相邻的字符 $t[i] \neq t[i+1],\ (1 \leq i \leq m-1)$，即不存在偶数长度的回文子串

因此只需考虑奇数长度的回文子串

而显然无论奇数长度的回文子串的中心是插入的字符或者是原串中的字符，其左右两端点的字符都是插入的字符

此时有 $\frac{len}{2}$ 个原串中的字符，有 $\frac{len}{2}+1$ 个插入的字符，故原串最长回文子串长度为 $\frac{len}{2}$

证明新串最长回文子串恰好是原串最长回文子串加上插入的字符这一过程省略。

2.5 算法步骤

记通过上述小技巧处理后的新字符串为 $s$，要求出从任意位置 $i$ 出发，向两边最远扩展的回文子串长度

我们把向一边能够扩展的字符数记为从 $i$ 开始的 最大回文半径，记作 $p[i]$，需要注意的是 $p[i]$ 包括 $i$ 自身

我们从左向右依次计算 $p[i]$

假设我们要计算 $p[i]$，此时已经计算了 $p[1],p[2],\cdots,p[i-1]$

为了计算 $p[i]$，在枚举 $i$ 的过程中，我们要维护使得 $R$ 最大的区间 $[L,R]$

其中 $\begin{cases}L=M-p[M]+1& (M<i)\\R=M+p[M]-1& (M<i)\end{cases}$

接着进行分类讨论：

• $i \leq R$：找到 $i$ 关于 $M$ 的对称点 $k$（此时 $i-M=M-k$，即 $k=2M-i$）
  • $p[k]$ 对应的回文区间 $[k-p[k]+1,k+p[k]-1]$ 不包含左端点 $L$
    • 即 $L<k-p[k]+1$
    • 又 $L=2M-R$ 且 $k=2M-i$
    • 则 $2M-R<2M-i-p[k]+1$，即 $p[k]<R-i+1$
    • 此时 $[k-p[k]+1,k+p[k]-1]$ 包含于 $[L,R]$
    • 故 $p[i]=p[k]$，且 $s[i-p[i]] \neq s[i+p[i]]$
    • 因此无需暴力向两边扩展
  • $p[k]$ 对应的回文区间 $[k-p[k]+1,k+p[k]-1]$ 包含左端点 $L$
    • 即 $L \ge k-p[k]+1$
    • 又 $L=2M-R$ 且 $k=2M-i$
    • 则 $2M-R \ge 2M-i-p[k]+1$，即 $R-i+1 \leq p[k]$
    • 此时 $[L,2k-L]$ 是回文串
    • 又 $[L,R]$ 是回文串
    • 则 $[2i-R,R]$ 也是回文串
    • 故 $p[i]=R-i+1$
    • 然后再暴力向两边扩展即可
• $i>R$
  • $p[i]=1$
  • 直接暴力向两边扩展即可

每轮循环后更新 $M、L、R$

最后找到所有 $p[i]$ 中的最大值 $x$，易得此时 $x=\frac{len}{2}+1$，因此最终答案为 $x-1$

复杂度分析：暴力扩展的过程中 $R$ 的值也在同步增加，$R$ 最多只会增加 $O(n)$ 次，因此总时间复杂度为 $O(n)$

2.6 代码模板

int manacher(string s){
    int n=(int)s.size();
    vector<int> p(2*n+2);
    vector<char> t(2*n+2);
    int m=0;
    t[++m]='$';
    for(int i=0;i<n;i++){
        t[++m]=s[i];
        t[++m]='$';
    }
    int M=0,R=0;
    for(int i=1;i<=m;i++){
        if(i>R)p[i]=1;
        else p[i]=min(p[2*M-i],R-i+1);
        while(i-p[i]>=1&&i+p[i]<=m&&t[i-p[i]]==t[i+p[i]])p[i]++;
        if(i+p[i]-1>R)M=i,R=i+p[i]-1;
    }
    return *max_element(p.begin(),p.end())-1;
}

2.7 例题

2.7.1 【模板】manacher 算法

题目描述：求字符串的最长回文子串的长度

题目分析：模板题

参考代码：

#include<bits/stdc++.h>
using namespace std;

int manacher(string s){
    int n=(int)s.size();
    vector<int> p(2*n+2);
    vector<char> t(2*n+2);
    int m=0;
    t[++m]='$';
    for(int i=0;i<n;i++){
        t[++m]=s[i];
        t[++m]='$';
    }
    int M=0,R=0;
    for(int i=1;i<=m;i++){
        if(i>R)p[i]=1;
        else p[i]=min(p[2*M-i],R-i+1);
        while(i-p[i]>=1&&i+p[i]<=m&&t[i-p[i]]==t[i+p[i]])p[i]++;
        if(i+p[i]-1>R)M=i,R=i+p[i]-1;
    }
    return *max_element(p.begin(),p.end())-1;
}

int main(){
    string s;
    cin>>s;
    cout<<manacher(s);
    return 0;
}

2.7.2 Palisection

题目描述：给定一个由小写字母组成的字符串 $s$，求出 $s$ 中有多少对有公共部分的回文子串。$1\leq|s|\leq2*{10}^{6}$

题目分析：

有公共部分的回文子串对=回文字串对-没有公共部分的回文子串对

$\text{回文子串对}=\frac{\text{回文子串}*(\text{回文子串-1})}{2}$

回文子串可通过 $p[i]$ 求出

没有公共部分的回文子串对与两部分相关：

1. 以 $i$ 结尾的回文子串数
2. 以大于 $i$ 开头的回文子串数

可以通过前缀和与后缀和求出上面两个值

每一种操作都是 $O(n)$，且互不相关，因此总时间复杂度为 $O(n)$

参考代码：

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int mod=51123987;

int manacher(string s){
    int n=(int)s.size();
    vector<int> p(2*n+2),f(n+2),v(n+2);
    vector<char> t(2*n+3);
    int m=0;
    t[++m]='$';
    for(int i=0;i<n;i++){
        t[++m]=s[i];
        t[++m]='$';
    }
    int M=0,R=0;
    for(int i=1;i<=m;i++){
        if(i>R)p[i]=1;
        else p[i]=min(p[2*M-i],R-i+1);
        while(i-p[i]>=1&&i+p[i]<=m&&t[i-p[i]]==t[i+p[i]])++p[i];
        if(i+p[i]-1>R)M=i,R=i+p[i]-1;
    }
    ll x=0;
    for(int i=1;i<=m;i++){
        int l=(i-p[i]+2)/2,r=i/2;
        ++v[l];--v[r+1];
        l=(i+1)/2,r=(i+p[i]-2)/2;
        ++f[l];--f[r+1];
        x+=r-l+1;
    }
    for(int i=1;i<=n+1;i++)
        v[i]+=v[i-1];
    for(int i=1;i<=n;i++)
        f[i]+=f[i-1];
    for(int i=n-1;i;i--)
        v[i]+=v[i+1],v[i]%=mod;
    ll ans=0;
    if(x&1)ans=x%mod*((x-1)/2%mod)%mod;
    else ans=x/2%mod*((x-1)%mod)%mod;
    for(int i=1;i<=n;i++){
        ans-=(ll)f[i]*v[i+1]%mod;
        if(ans<0)ans+=mod;
    }
    return ans;
}

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    cout<<manacher(s);
    return 0;
}

---

3. 最小表示法

3.1 基础知识

对于一个长度为 $n$ 的字符串 $s$，我们把它首位相连形成一个环，然后在任一位置断开，得到的字符串 $t$ 与 $s$ 循环同构

即若 $t$ 与 $s$ 循环同构，则满足 $t_i=s[i] \cdots s[n]+s[1] \cdots s[i-1],\ (1 \leq i \leq n)$

在这 $n$ 个与 $s$ 循环同构的字符串中，字典序最小 的那个称为 $s$ 的 最小表示

3.2 最小表示的求法

暴力做法是把这 $n$ 个与 $s$ 循环同构的字符串都求出来，然后选择字典序最小的，显然复杂度为 $O(n^2)$

考虑这样的优化：将 $s$ 复制一遍加到 $s$ 后面，这时与 $s$ 循环同构的字符串都是新串的长度为 $n$ 的子串

上述优化对于时间复杂度没有影响，一种更快的做法是二分+哈希，可将时间复杂度降低至 $O(nlogn)$

而使用最小表示法可以在线性时间复杂度内解决这一问题

3.3 最小表示法

用两个指针 $i$ 和 $j$，分别指向到目前为止两个可能是答案串的起始位置

初始 $i=1,\ j=2$，随着算法进行，两者逐步增大

假设 $i<j$，且从 $i$ 开始的 最大 的 $k$ 位字符和从 $j$ 开始的 最大 的 $k$ 位字符是一样的

此时 $s[i] \cdots s[i+k-1] \ = \ s[j] \cdots s[j+k-1], \ (k \leq n)$

分如下三种情况进行进一步讨论：

1. $s[i+k]>s[j+k]$

   位置 $i$ 显然不可能是最终答案，$i$ 指针需要向后挪

   注意到 $s[i] \cdots s[i+k-1]$ 和 $s[j] \cdots s[j+k-1]$ 完全相等，且 $s[i+k]>s[j+k]$

   那么 $i$ 到 $i+k$ 都不可能是答案

   所以 $i$ 可以直接挪到 $i+k+1$ 的位置，注意此时 $i$ 可能会大于等于 $j$，两者相等时我们可以随便选择一个指针把它向后挪一位

2. $s[i+k]<s[j+k]$

   位置 $j$ 不可能是最终答案，$j$ 指针需要向后挪

   $j$ 到 $j+k$ 都不可能是答案，$j$ 可以直接挪到 $j+k+1$ 的位置

3. $s[i+k]=s[j+k]$

   这种情况其实代表算法已经终止

算法会在 $i$ 或 $j$ 之一大于 $n$ 的时候终止

此时仍然保留在字符串范围内的指针指向的位置就是要求的答案

3.4 代码模板

string getmin(string s){
    int n=(int)s.size();
    s="#"+s+s;
    int i=1,j=2;
    while(j<=n){
        int k=0;
        while(k<n&&s[i+k]==s[j+k])k++;
        if(s[i+k]>s[j+k])i+=k+1;
        else j+=k+1;
        if(i==j)j++;
        if(i>j)swap(i,j);
    }
    return s.substr(i,n);
}

3.5 例题

3.5.1 【模板】最小表示法

题目描述：求整数序列的最小表示

题目分析：模板题

参考代码：

#include<bits/stdc++.h>
using namespace std;

int getmin(vector<int> &s){
    int n=(int)s.size();
    for(int i=1;i<=n;i++)s.push_back(s[i]);
    int i=1,j=2;
    while(j<=n){
        int k=0;
        while(k<n&&s[i+k]==s[j+k])k++;
        if(s[i+k]>s[j+k])i+=k+1;
        else j+=k+1;
        if(i==j)j++;
        if(i>j)swap(i,j);
    }
    return i;
}

int main(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    int st=getmin(a);
    for(int i=st;i<st+n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

---

全文结束，谢谢阅读！

---

最后更新: 2023-01-05 14:02:20

评论