字符串匹配就是在主串 \(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\)

输入样例：
\( \text{8 3}\\ \text{aabbaabb}\\ \text{1 3 5 7}\\ \text{1 3 6 8}\\ \text{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;
    }
}

原题链接：

• 字符串哈希

算法三：KMP

待更新