字符串匹配问题（哈希算法与kmp算法）

字符串匹配问题（哈希算法与kmp算法）

引用

CSDN

1.

https://blog.csdn.net/hhh123Dora/article/details/146437007

字符串匹配是计算机科学中的一个基本问题，广泛应用于文本搜索、数据处理等领域。本文将介绍两种常用的字符串匹配算法：KMP算法和哈希算法。通过详细的步骤讲解和代码实现，帮助读者理解这两种算法的原理和应用场景。

一、题目再现

题目链接：#103. 子串查找 - 题目 - LibreOJ

二、题目分析

题目要求我们计算字符串 B 在字符串 A 中出现的次数，且 B 在 A 中的出现是可以重叠的。例如：

输入：

zyzyzyz
zyz

输出：

3

解释：
B="zyz"在 A="zyzyzyz"中出现了 3 次，分别是在位置 0、2 和 4。这些出现是可以重叠的，比如从位置 0 开始的 B 和从位置 2 开始的 B 共享了中间的字符。

数据范围

A 和 B 的长度最大为 1e6。
A 和 B 仅包含大小写字母。

这意味着我们需要一个高效的算法来解决这个问题，暴力匹配法（时间复杂度 O(n⋅m) ）在最大数据范围下会超时。对于这种字符串匹配问题，我们可以用KMP或者哈希来解决。

三、KMP算法

一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。 ——KMP

3.1 简介

KMP算法（Knuth-Morris-Pratt 算法）是一种高效的字符串匹配算法，用于在一个主字符串（文本）中查找一个子字符串（模式）的出现位置。它的核心思想是通过预处理模式字符串，构建一个部分匹配表（next数组），从而在匹配过程中避免不必要的回溯，将时间复杂度从暴力匹配的 O(n⋅m) 优化到 O(n+m)，其中 n 是主字符串的长度，m 是模式字符串的长度。

（看不懂，没关系，主波举个例子带你学）

想象一下，你是一个渔夫，正在一片大海（主字符串 A）中捕捞一种特定的鱼（模式字符串 B）。如果你用普通的渔网（暴力匹配法），每次捞不到鱼时，你都需要把渔网完全收回来，再重新撒网，效率非常低。而 KMP 算法则像是一个智能渔网，它会根据鱼的“逃跑路线”（next数组），快速调整渔网的位置，避免重复劳动。

通过例子理解 KMP

例子：
主字符串 s="ABABABCABABC"
模式字符串 t="ABABC"

我们的目标是在 s 中找到 t 的所有出现位置。

3.2 步骤

第一步，构建next数组

由于next是 C++ 标准库中的一个函数名称，因此不能直接用作变量名，故在代码中使用的ne。ne数组记录了模式字符串 tt 的“逃跑路线”。它的定义是：对于模式字符串的每个位置 i，ne[i]表示前 i 个字符组成的子串中，最长的相等前缀和后缀的长度。

前缀和后缀的定义

• 前缀：从字符串开头开始的子串。
• 比如字符串"ABABC"的前缀有："A"，"AB"，"ABA"，"ABAB"。
• 后缀：从字符串结尾结束的子串。
• 比如字符串"ABABC"的后缀有："C"，"BC"，"ABC"，"BABC"。

最长相等前缀和后缀

对于模式字符串 t="ABABC"，我们逐个位置分析：

next数组：[0, 0, 1, 2, 0]

代码实现：

void getnext() {
    int n = t.size(); // 模式字符串的长度
    ne[0] = 0;       // 第一个字符没有前缀和后缀
    for (int i = 1, j = 0; i < n; i++) {
        // 如果当前字符不匹配，回溯到 ne[j-1]
        while (j > 0 && t[i] != t[j]) j = ne[j - 1];
        // 如果当前字符匹配，j 向前移动
        if (t[i] == t[j]) j++;
        // 记录 ne[i]
        ne[i] = j;
    }
}

在补全代码可以打印出结果如下：

第二步，匹配过程

利用next数组在主字符串 s 中查找模式字符串 t 的出现次数。

代码实现：

int kmp() {
    int ans = 0; // 记录匹配次数
    int n = s.size(), m = t.size(); // 主字符串和模式字符串的长度
    for (int i = 0, j = 0; i < n; i++) {
        // 如果当前字符不匹配，回溯到 next[j-1]
        while (j > 0 && s[i] != t[j]) j = ne[j - 1];
        // 如果当前字符匹配，j 向前移动
        if (s[i] == t[j]) j++;
        // 如果模式字符串完全匹配，计数器加 1，并回溯 j
        if (j == m) {
            ans++;
            j = ne[j - 1];
        }
    }
    return ans;
}

匹配过程分解：

3.3 AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N=1e6+9; 
string s,t;
int ne[N];
void getnext(){
    int n=t.size();
    ne[0]=0;
    for(int i=1,j=0;i<n;i++){
        while(j>0&&t[i]!=t[j]) j=ne[j-1];
        if(t[i]==t[j]) j++;
        ne[i]=j;
    }
}
int kmp(){
    int ans=0;
    int n=s.size(),m=t.size();
    for(int i=0,j=0;i<n;i++){
        while(j>0&&s[i]!=t[j]) j=ne[j-1];
        if(s[i]==t[j]) j++;
        if(j==m) ans++,j=ne[j-1];
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0); 
    cin>>s>>t;
    getnext();
    cout<<kmp(); 
    return 0;
}   

四、哈希算法

人生的智慧不在于完美避开所有矛盾，而在于冲突降临时，能以独特的方式为不同的自己找到共存的位置。——HASH

4.1 简介

哈希算法（Hash Algorithm）是一种将任意长度的输入数据（如字符串、文件等）转换为固定长度的输出（通常是一串十六进制数字）的数学函数。

而在本文中，我们可以构建哈希表来解决这道题。

哈希表（Hash Table），也称为散列表，是一种高效的数据结构，用于实现键值对（Key-Value）存储和快速查找。它通过哈希函数（Hash Function）将键（Key）映射到存储位置（Bucket），从而实现平均 O(1) 时间复杂度的插入、删除和查找操作。

通俗的来说，就是把一个比较大的范围，通过映射给它缩小至某一个小范围内，通常就是对其取模，比如想将1e-91e9缩小至01e5，那么就可以对1e-9%N，1e9%N，由于在C++中对负数取模结果还是负数，那么可以（K%N+N）%N，这样就可以取正了，然后这个N其实就是在我们要缩小范围的数的最近的一个质数，而且要离2的整次幂尽可能的远。

再形象一点就是，如何把大海装进小池塘

想象你有一个巨大的海洋（数据范围可能是-10亿到+10亿），但你现在只有一个小池塘（比如容量10万）来养鱼（存储数据）。哈希表就是解决这个问题的神奇渔网：

• 渔网（哈希函数）：不管多大的鱼（数据），一网捞上来后都按一定规则给它分配一个小池塘的编号
• 取模运算：最常用的"分配规则"就是取模，比如鱼的大小 % 100000
  但
  如果鱼是-3米长（虽然实际上并不存在，假设一下），
  -3 % 10 = -3
  （直接取模还是负数），而我们希望所有鱼都放在0-9号池塘，解决方法就像给鱼量身高时

int pond_number = (fish_size % N + N) % N;

相当于：

1. 第一次量：-3 % 10 = -3
   （还是负数）
2. 加个补偿：-3 + 10 = 7
   （现在正了）
3. 再确认：7 % 10 = 7
   （确保在0-9之间）

为什么选质数：避免鱼群扎堆

选择池塘大小（N）有讲究：

• 不选2的幂次：比如选1024（2¹⁰），鱼的大小如果是1024的倍数，就会全部挤在0号池塘
• 选质数：比如10007，就像把渔网的网眼设计成不规则形状，能让鱼更均匀分布

就像：

• 如果你用偶数大小的渔网（比如10），所有偶数大小的鱼都会挤在偶数编号的池塘
• 但用质数大小的渔网（比如11），鱼会分散得更均匀

哈希一般有拉链法和开放寻址法，但本文是字符串哈希解决这个问题，故前两种方法等下次遇到再写，接下来主要讲字符串哈希

4.2 字符串哈希的步骤

第一步：预处理，计算字符串所有前缀的哈希值，并存储幂次表。

1.选择两个参数：
基数p：通常取 131 或 13331（经验值，减少冲突）
模数q：取 2⁶⁴（利用unsigned long long自然溢出，省去显式取模）

2.初始化：

const int P = 131;                    // 基数
unsigned long long h[N], p[N];        // h存前缀哈希，p存幂次
p[0] = 1;                            // p^0 = 1
h[0] = 0;                            // 空串哈希为0

3.计算前缀哈希和幂次

for (int i = 1; i <= str.size(); i++) {
    h[i] = h[i-1] * P + str[i-1];    // 递推计算哈希
    p[i] = p[i-1] * P;               // 计算p^i
}

第二步，计算子串哈希

对于子串str[L..R]：

代码实现：

unsigned long long get_hash(int L, int R) {
    return h[R] - h[L-1] * p[R-L+1];
}

看起来有点像前缀和

注意

1.字符不能映射为0

• 例如：若'A'=0，则"A"和"AA"的哈希均为 0，导致冲突。
• 解决：直接用ASCII码，或映射为str[i]-'a'+1。

2.自然溢出替代取模

// 利用unsigned long long自动模2^64
h[i] = h[i-1] * P + str[i-1];  // 无需显式 % Q

4.3 AC代码

#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int N=1e6+9;
string a,b;
int P=131,na,nb,ans;
ull h[N],p[N]; 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>a>>b;
    na=a.size(),nb=b.size();
    
    //处理p的幂次 
    p[0]=1;
    for(int i=1;i<na;i++) p[i]=p[i-1]*P;
    
    //计算字符串b的哈希值 
    ull hb=0;
    for(int i=0;i<nb;i++) hb=hb*P+b[i];
    
    //计算字符串a的前缀哈希
    h[0]=a[0];
    for(int i=1;i<na;i++) h[i]=h[i-1]*P+a[i];
    
    //统计次数 
    for(int i=nb-1;i<na;i++){
        ull ha;
        if(i-nb<0) ha=h[i];
        else ha=h[i]-h[i-nb]*p[nb];
        if(ha==hb) ans++;
    }
    cout<<ans; 
    return 0;
}   

4.5 再解释一些为什么

首先我们要先清楚字符串哈希的目的：
将任意长度的字符串映射为一个固定大小的数值（哈希值），并满足以下关键需求：
1.快速计算（O(1)或O(n)预处理后O(1)查询）
2.低冲突概率（不同字符串尽量映射到不同哈希值）
3.支持子串操作（能快速计算任意子串的哈希值）

1. 为什么用多项式哈希？

数学形式：

原因：

• 唯一性：多项式展开类似于将字符串视为一个p进制数，不同字符串几乎唯一对应不同值。
• 递推计算：前缀哈希可以通过递推公式高效计算：h[i]=h[i−1]×p+s[i]h
• 子串支持：通过前缀哈希的差分计算子串哈希（类似前缀和思想）：H(L,R)=h[R]−h[L−1]×pR−L+1

2. 为什么能快速计算子串哈希？

类比十进制数：
假设字符串是十进制数"1234"，要取子串"34"：
全串=1234, 前缀=12，那么子串=1234−12×10^2=34

推广到多项式：