字符串匹配就是在主串 $A$ 中查找子串 $B$ 。例如在 $\text{ abcabc}$ 中查找 $\text{bca}$ 是否存在。子串的长度 $≤$ 主串长度

比较容易实现的字符串匹配算法：

1. 暴力 $O(mn)$
2. 字符串哈希 $O(m+n)$
3. KMP算法 $O(m+n)$

算法一： 暴力

思路很简单：

让子串从第一个字符开始，与主串的每一个字符匹配，如果当前字符匹配上，则继续匹配下一个字符，如果匹配到子串的最后一个字符都相同，那就说明子串在主串中出现了。

例如：

算法二：字符串哈希

整体思路：

将一个字符串通过哈希函数变成数字，比较时只需比较数字是否相同即可。

获取哈希值的基本思路：

例如一个字符串 $\text{abc}$，把每个字符看成一个 P 进制的数字，那么有：

再利用前缀和，就可以处理出每个子串的哈希值。

如：

这里我们会想，要是有两个不同的字符串，对应同一个哈希值，那不就出问题了吗？

确实是这样，这个也叫做哈希冲突。所以我们为了避免哈希冲突，可以通过这种手段：

让 $P$ 取值为 $131$ 或者 $13331$ ，再将哈希值对 $2^{64}$ 取模，可以有效减少哈希冲突。

在代码上，我们可以用$\text{ unsigned long long}$ 类型来实现对 $2^{64}$ 取模的操作。

由于 $P$ 的次方经常用到，所以可以预处理出来。

例题：

给定一个长度为 $n$ 的字符串，再给定 $m$ 个询问，每个询问包含四个整数 $l1,r1,l2,r2$，请你判断 $[l1,r1]$ 和 $[l2,r2]$ 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 $n$ 和 $m$，表示字符串长度和询问次数。

第二行包含一个长度为 $n$ 的字符串，字符串中只包含大小写英文字母和数字。

接下来 $m$ 行，每行包含四个整数 $l1,r1,l2,r2$，表示一次询问所涉及的两个区间。

注意，字符串的位置从 $1$ 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

$1≤n,m≤105$

输入样例：

8 3 aabbaabb 1 3 5 7 1 3 6 8 1 2 1 2

输出样例：

Yes No Yes

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10,P = 131;
unsigned long long p[N],h[N];
unsigned long long find(int l,int r)
{
    return h[r] - h[l-1]*p[r-l+1];
}
int main()
{
    int n,m;
    string s;
    cin >>n>>m;
    cin >>s;
    s = ' '+s;
    p[0] = 1;
    for (int i=1;i<=n;i++)
    {
        p[i] = p[i-1]*P;
        h[i] = h[i-1]*P + s[i];
    }
    while (m--)
    {
        int l1,r1,l2,r2;
        cin >>l1>>r1>>l2>>r2;
        if (find(l1,r1) == find(l2,r2)) cout <<"Yes"<<endl;
        else cout <<"No"<<endl;
    }
}

原题链接：

• 字符串哈希

算法三：$\text{KMP}$

大名鼎鼎的 $\text{KMP}$ 算法并不是很好理解，在这里仅作为思考。

首先，我们知道了暴力匹配算法，但其实在暴力匹配的过程中，我们做了很多不必要的操作。比如在字符串 $\text{ABABABCAA}$ 中查找子串 $\text{ABABC}$ ，如果用暴力做法，我们在第一遍匹配的时候，会发现子串的最后一个字母 $\text{C}$ 与主串的字母 $\text{A}$ 不相同，然后子串又从第一位，主串从第二位开始匹配。但其实在这个过程中，我们已经匹配上了 $\text{ABAB}$ ，下一次匹配只需要从主串的第五位，子串的第三位开始匹配。 像这样：

我们为什么可以这样做呢？

因为在第一次匹配的时候，我们发现已经匹配上的 $\text{ABAB}$ 前后缀是有公共部分 $\text{AB}$ 的。

这里为我们提供了一个思路，如果可以知道每次匹配到不相同，我们的子串应该移动到哪个位置再继续匹配，那可以大大加快匹配的速度。这里我们发现，主串的指针其实不需要回退，只要子串的指针移动到正确的位置即可。

那我们的子串应该移动到哪个位置呢？

这里引入一个 $\text{next}$ 数组，${next[j]}$ 代表 $j$ 指针应该移动到的下标。

先不说 $\text{next}$ 数组是怎么得到的，来看一个例子：

对照这个表，再进行一次匹配：

我们发现在指针 $i$ 和 $j+1$ 的位置的字符不匹配，所以让 $j$ 变成 ${next[j]}$ 的值，也就是 $2$ ，然后继续进行匹配：

注：我们这里每次比较的是主串的 $i$ 指向的字符和子串 $j+1$ 指向的字符。

匹配的代码可以这样实现：

//s是主串 p是子串
for (int i=1,j=0;i<=n;i++)
{
    while (j && s[i] != p[j+1]) j = ne[j]; //如果不匹配，j一直后退到能匹配 或者一直退到起点 j=0
    if (s[i] == p[j+1]) j++;
    if (j == m) //这里是匹配成功了，如果要继续匹配就让 j = ne[j] 继续匹配
    {
        j = ne[j];
    }
}

$\text{next}$数组的求法比较难理解，不过多介绍。这里我们认为求$\text{next}$数组的过程，是子串自己与自己匹配的过程。

//ne[1] = 0
for (int i=2,j=0;i<=n;i++)
{
    while (j && p[i] != p[j+1]) j = ne[j];
    if (p[i] == p[j+1]) j++;
    ne[i] = j; //记录下next数组
}

例题：

• KMP字符串