字符串（字符串匹配）

article/2025/10/4 1:08:04

一、字符串匹配问题、基础

1、假设文本是一个长度为n的数组T，而模式是长度为m的数组P，我们希望在文本T中寻找模式P

如果P出现在T中的第s个位置，那么我们称其有效偏移为s，在其他不匹配的位置称为无效偏移

2、如果字符串w是字符串x的前缀，可以记作 $w\sqsubset x$ ，后缀可以记为 $w\sqsupset x$

引理：如果x、y都是z的后缀，如果x.size<y.size那么x是y的后缀；如果x.size=y.size则x=y

3、如果应用暴力匹配，那么对每个偏移量都会进行匹配，那么复杂度 $O((n-m+1)m)$

二、Rabin-Karp算法

1、利用字符串的hash值进行匹配，而不是逐位进行比较。在计算hash值时，可以先计算出模式串长度的hash值，然后前面“减”一位，后面“加”一位，可以求出母串所有长为m的hash值，进而匹配

2、如果hash值过大，可以进行取模，那么可能出现hash冲突，此时需要进行显示匹配（如果hash值不同那么一定不匹配）。此时的算法是在快速检测无效偏移

三、有限自动机

自动机用通俗的话讲，就是不断向一个机器里面输入内容，然后机器会根据现在的状态和输入的内容达到下一个状态。

一个有限自动机M，是一个五元组 $(Q,q_0,A,\sum ,\delta )$ 其中，

$Q$ 是状态的有限集合；（可能出现的状态）

$q_0\in Q$ 是初始状态；（最开始的状态）

$A\subseteq Q$ 是一个特殊的接收状态集合；（满足题意的状态）

$\;$ $\sum$ 是有限输入集合；（可能的输入）

$\delta$ 是一个从 $Q\times\sum$ 到 $Q$ 的函数，称为M的转移函数；（从一个状态转向另一个状态的函数）

有限自动机开始于状态 $q_0$ ,每次读入一个字符，如果在状态q是读入字符a，那么他会从状态q变成状态 $\delta (q,a)$ （进行了一次转移），当 $q\in A$ 时，就说自动机M接受了迄今为止所读入的字符串，没有被接受的输入称为被拒绝的输入

如上图就是模式串ababaca的状态转换图

四、KMP算法

1、匹配原理

为了减少重复过程，可以选择j来优化匹配位置，而j取决于当前字符之前的串的前后缀的相似度，而这个前后缀的相似度就用next数组来记录

如果前缀和后缀相同，就用前缀对齐后缀，下一位从字符开始重新匹配

匹配的过程可以利用有限状态自动机来理解

2、next数组

含义：从第j（字符串和下标j从0开始）个（不包括j）向前k个元素与从第1个向后k个元素相同，k就是next[j]的值

换种解释方法：next[i]（字符串和下标i从1开始）表示s中以s[i]结尾的非前缀子串与s的前缀能匹配的最长长度

next数组从0到len，一共有len+1个位置，第一个位置0对应字符串第一个位置，最后一个位置len对应字符串的尾后位置（next数组此时对应是前面整个字符串能匹配的最长前后缀）

3、求next数组

如果j == -1就开始向前匹配，如果s[i] == s[j]填next数组并向后匹配

if (j == -1 || s[i] == s[j])nex[++i] = ++j;

如果没有匹配上，就到s[j]的前面的字符串的能匹配到的最长的前后缀

比如：abac......abax，i到x位置，j到c位置，不相等，那么就到nex[3]=1位置

elsej = nex[j];

4、代码

//以-1开头的next数组中存的是匹配失败时要去字符串的下标（该下标前nex[j]个无需重复匹配）
int nex[maxn];
void getnext(string s)
{int i, j;i = 0; j = -1;nex[0] = -1;while (i < s.size()){if (j == -1 || s[i] == s[j])nex[++i] = ++j;elsej = nex[j];}
}

int kmp(string a, string b)		//a母串，b模式串
{int ans = 0;getnext(b);int i = 0, j = 0;while (i < a.size()){if (j == -1 || b[j] == a[i]){++i;++j;}else j = nex[j];if (j == b.size()){ans++;j = nex[j];}}return ans;
}