一、基础知识

1. 字符串匹配

给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l,r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。保证 $1\le |s1|,|s2|\le 10^6$。

上述是一个经典的字符串匹配（$1$ 对 $1$）问题。

(1) 简单暴力

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

• 枚举序列匹配时的出现位置 $l$
• 检查此时匹配的每一个位置是否相同，如果全部相同则记录答案

(2) 字符串哈希

时间复杂度：$O(n+m)$

• 把字符串看作一个 BASE 进制的大数，将其映射为一个整数
• 预先算出文本串所有前缀的哈希值，这样就能 $O(1)$ 地算出任意子串的哈希值
• 算出 $s_2$ 的哈希值，再枚举 $s_1$ 中每个长度为 $|s_2|$ 的子串的哈希值，看两者数字是否相等

(3) KMP

• 预处理模式串生成 next[]
• 利用已匹配的信息避免回溯

如你所见，$\text{KMP}$ 的核心在于前缀函数的预处理，通过避免冗余匹配提升效率。因此，我们成功将时间复杂度优化至线性 $O(n+m)$。

2. 前置概念

(1) 前缀

即 $\mathrm{pre}(s,k)$，是从字符串 $s$ 中取前 $k$ 个字符构成的字符串

(2) 后缀

即 $\mathrm{suf}(s,k)$，是从字符串 $s$ 中取后 $k$ 个字符构成的字符串，当 $k=0$ 时为空串。

(3) Border

若整数 $r$ 满足 $0<r<|s|$ 且 $\mathrm{pre}(s,r)=\mathrm{suf}(s,r)$，则称 $\mathrm{pre}(s,r)$ 为 $s$ 的一个 $\text{Border}$。

一个字符串可能有多个 $\text{Border}$，例如对于 $s=\mathrm{abcabcab}$，$\mathrm{ab}$ 和 $\mathrm{abcab}$ 是 $s$ 的 $\text{Border}$。记 $\mathrm{lps}(s)$ 表示字符串 $s$ 的最长 $\text{Border}$。

3. P3375 【模板】KMP

【KMP 模版】

模版背诵熟练即可，两个函数做到能完整默写，具体原理稍微有点复杂。

#include<bits/stdc++.h>
using namespace std;
const int MAXL=1e6+8;
string s1,s2;
int lps[MAXL],ocnt,occ[MAXL];//lps[i]:s2[1,i]的最长相等前后缀长度
void get_lps(const string&s){
    int len=s.size()-1;
    for(int i=2,j=0;i<=len;i++){//s1[...,i-1]与s2[1,j]匹配
        while(j>0&&s[i]!=s[j+1])j=lps[j];
        if(s[i]==s[j+1])j++;
        lps[i]=j;
    }
}
void kmp(const string&s,const string&t){
    ocnt=0;
    int slen=s.size()-1,tlen=t.size()-1;
    if(tlen==0)return;
    get_lps(t);
    for(int i=1,j=0;i<=slen;i++){//s1[...,i-1]与s2[1,j]匹配
        while(j>0&&s[i]!=t[j+1])j=lps[j];
        if(s[i]==t[j+1])j++;
        if(j==tlen)occ[++ocnt]=i-j+1,j=lps[j];
    }
}
int main(){
    cin>>s1>>s2,s1="#"+s1,s2="#"+s2;
    kmp(s1,s2);
    for(int i=1;i<=ocnt;i++)cout<<occ[i]<<"\n";
    for(int i=1;i<s2.size();i++)cout<<lps[i]<<" ";
    return 0;
}

二、延伸知识

1. exKMP

(1) 定义

扩展 $\text{KMP}$ 算法（$\text{Extended KMP}$），通常也称为 $Z$ 函数，它解决的问题是：给定一个文本串 $S$ 和模式串 $P$，求 $P$ 与 $S$ 的每一个后缀的最长公共前缀（$\text{LCP}$）的长度。

其中，$Z_1$ 通常定义为 $0$ 或字符串总长 $n$。

示例：

• $\text{aaaaa}z(\text{aaaaa})=[5,4,3,2,1]$
• $\text{aaabaab}z(\text{aaabaab})=[7,2,1,0,2,1,0]$
• $\text{abacaba}z(\text{abacaba})=[7,0,1,0,3,0,1]$

扩展 $\text{KMP}$ 算法通常需要计算两个数组：

1. $Z$ 数组（仅单个字符串自身）
   对于字符串 $P$，$Z[i]$ 表示子串 $P[i\dots n]$（从第 $i$ 位开始的后缀）与整串 $P[1\dots n]$ 的最长公共前缀长度。

2. $\text{Ext}$ 扩展数组（文本串 $S$ $+$ 模式串 $P$）
   $\text{Ext}[i]$ 表示：模式串 $P$ 与文本串从第 $i$ 位开头的后缀 $S[i\dots m]$的最长公共前缀长度。

核心：维护已知信息的最右区间 $[l,r]$。

(2) 模版

【扩展 KMP / exKMP（Z 函数）模版】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXL=2e7+8;
string s1,s2;
int lcp[MAXL],ext[MAXL];
void get_lcp(const string&s){
    int len=s.size()-1,l=1,r=0;
    lcp[1]=len;
    for(int i=2;i<=len;i++){
        if(i<=r)lcp[i]=min(lcp[i-l+1],r-i+1);
        while(i+lcp[i]<=len&&s[i+lcp[i]]==s[1+lcp[i]])lcp[i]++;
        if(i+lcp[i]-1>r)l=i,r=i+lcp[i]-1;
    }
}
void exkmp(const string&s,const string&t){
    int slen=s.size()-1,tlen=t.size()-1,l=1,r=0;
    if(tlen==0)return;
    get_lcp(t);
    while(r+1<=slen&&r+1<=tlen&&s[r+1]==t[r+1])r++;
    ext[1]=r;
    for(int i=2;i<=slen;i++){
        if(i<=r)ext[i]=min(lcp[i-l+1],r-i+1);
        while(i+ext[i]<=slen&&1+ext[i]<=tlen&&s[i+ext[i]]==t[1+ext[i]])ext[i]++;
        if(i+ext[i]-1>r)l=i,r=i+ext[i]-1;
    }
}
int main(){
    cin>>s1>>s2,s1="#"+s1,s2="#"+s2;
    exkmp(s1,s2);
    ll ans1=0,ans2=0;
    for(int i=1;i<s2.size();i++)ans1^=1ll*i*(lcp[i]+1);
    for(int i=1;i<s1.size();i++)ans2^=1ll*i*(ext[i]+1);
    cout<<ans1<<"\n"<<ans2;
    return 0;
}

2. 马拉车算法

(1) 定义

由于作者也没有搞懂，所以待会回来搞一搞。

(2) 模版

【Manacher 算法模版】

#include<bits/stdc++.h>
using namespace std;
const int MAX2L=2e6+8;
string s;
int rad[MAX2L];
void manacher(const string&s){
    string t="$#";
    for(char ch:s)t+=ch,t+='#';
    int len=t.size()-1,l=1,r=0;
    for(int i=1;i<=len;i++){
        if(i<=r)rad[i]=min(rad[l+r-i],r-i+1);
        while(i-rad[i]>=1&&i+rad[i]<=len&&t[i-rad[i]]==t[i+rad[i]])rad[i]++;
        if(i+rad[i]-1>r)l=i-rad[i]+1,r=i+rad[i]-1;
    }
}
int main(){
    cin>>s;
    manacher(s);
    int ans=0,len=s.size()*2-1;
    for(int i=1;i<=len;i++)ans=max(ans,rad[i]-1);
    cout<<ans;
    return 0;
}

三、经典例题

1. P4391 [BalticOI 2009] Radio Transmission 无线传输

【[BalticOI 2009] Radio Transmission 无线传输】

易证：$\text{ans}=L-{\text{lps}}_L$（可视作 $\text{lps}$ 的一个性质）。

例如：$s=$ cabcabca，则 ${\text{lps}}_L=5$（cabca），循环节为 $L-{\text{lps}}_L=8-5=3$。

#include<bits/stdc++.h>
using namespace std;
const int MAXL=1e6+8;
int n;
string s;
int lps[MAXL],ocnt,occ[MAXL];//lps[i]:s.substr(1,i)的最长相等前后缀长度
void get_lps(const string&s){
    int len=s.size()-1;
    for(int i=2,j=0;i<=len;i++){//s[...,i-1]与s[1,j]匹配
        while(j>0&&s[i]!=s[j+1])j=lps[j];
        if(s[i]==s[j+1])j++;
        lps[i]=j;
    }
}
int main(){
    cin>>n>>s,s="#"+s;
    get_lps(s);
    cout<<n-lps[n];
    return 0;
}

2. 其他常见问题

(1) 最短周期

• 最优（$\text{KMP}$）：$ans=|s|-\text{lps}[|s|]$
• $\text{Z}$ 函数：计算 $s$ 的 $\text{Z}$ 函数，找到最小的 $i\mid (|s|)$，使得 $i+z_{i+1}=|s|$

(2) 所有 border

• 最优（$\text{KMP}$）：令 $r=\text{lps}[|s|]$，循环执行 $r=\text{lps}[r]$，每次得到的 $r$ 为合法 $\text{border}$ 长度
• $\text{Z}$ 函数：计算 $s$ 的 $\text{Z}$ 函数， ∀ i ∈ { 1 , 2 , … , ∣ s ∣ } ∧ i + z i − 1 = ∣ s ∣ \forall i\in\{1,2,\dots,|s|\}\land i+z_i-1=|s| ∀i∈{1,2,…,∣s∣}∧i+zi​−1=∣s∣，$s[i,i+z_i-1]$ 就是一个答案

(3) t 在 s 中的所有出现位置

• 最优（$\text{KMP}$）：预处理 $t$ 的 $\text{lps}$ 数组，双指针遍历 $s$ 匹配，完整匹配时记录起点，令 $j=\text{lps}[j]$ 继续匹配
• $\text{Z}$ 函数：构造 $t+\#+s$，计算其 $\text{Z}$ 函数， ∀ i ∈ { ∣ t ∣ + 2 , ∣ t ∣ + 3 , … , ∣ t ∣ + 1 + ∣ s ∣ } ∧ z i = ∣ t ∣ \forall i\in\{|t|+2,|t|+3,\dots,|t|+1+|s|\}\land z_i=|t| ∀i∈{∣t∣+2,∣t∣+3,…,∣t∣+1+∣s∣}∧zi​=∣t∣，$i-|t|-1$$就是一个答案的起始位置

(4) 最长回文前缀

• 最优（$\text{KMP}$）：构造翻转串 $s^{\prime }+\#+s$，求拼接串 $\text{lps}$ 数组，$\text{lps}[\text{len}(s^{\prime }+\#+s)]$ 即为答案
• $\text{Z}$ 函数：构造 $s+\#+s^{\prime }$，其中 $s^{\prime }$ 表示 $s$ 反转后的字符串，计算其 $\text{Z}$ 函数，然后从 $\#$ 后找到第一个 $i$ 使得 $i+z_i-1=2|s|+1$，$z_i$ 就是答案

(5) s 的每个后缀与 t 的 LCP

• 最优（扩展 $\text{KMP}$）：直接计算 $\text{Ext}$ 数组，$\text{Ext}[i]$ 为 $s$ 第 $i$ 个后缀与 $t$ 的 $\text{LCP}$
• $\text{Z}$ 函数：构造 $t+\#+s$，计算其 $\text{Z}$ 函数，$z_{|t|+2},z_{|t|+3},\dots ,z_{|t|+1+|s|}$ 即为答案

(6) 所有前缀出现次数

两种方法效率持平

• $\text{KMP}$ 写法：初始化 $cnt[i]=1$，倒序遍历 $i=|s|\to 2$，执行 $cnt[\text{lps}[i]]+=cnt[i]$

• $\text{Z}$ 函数：计算 $s$ 的 $\text{Z}$ 函数，$z_i$ 就相当于让长度为 $1\sim z_i$ 的前缀出现次数加 $1$，差分即可