题目描述

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

样例

输入样例：
3
aba
5
ababa

输出样例：
0 2

算法

(字符串哈希)

1. KMP算法已经很清楚了，所以用 字符串哈希来实现一个KMP算法的题，毕竟 字符串哈希很无敌。。
2. QAQ()函数的本质是 字符串哈希的本质，也就是求出一个子字符串的哈希值。
3. 首先读入主串s和模式串p，均从下标1开始。
4. 先求出模式串p的 P进制哈希值。
5. 接下来求出主串s的 P进制字符串前缀哈希值。
6. 接下来记录 P进制的每一位，存储到hp[N]数组中。
7. hp[N]数组长度跟模式串p的长度相等，不可以等于主串s的长度。会在大数据的时候SE，具体原因我还不清楚，有知道的大佬是否可以说一下？
8. 最后下标l从1开始，因为是对应的主串s，匹配是从下标1开始的。因为l = 1，所以对应的r = l + n - 1。最后输出起始下标，所以是l - 1。

时间复杂度

$O(n)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010, P = 131;

#define ULL unsigned long long

ULL hs[M], hp[N];
int n, m;
char s[M], p[N];

ULL QAQ(int l, int r)
{
    return hs[r] - hs[l - 1] * hp[r - l + 1];
}

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    ULL hap = 0;
    for(int i = 1; i <= n; i ++) hap = hap * P + p[i];

    hs[0] = 0;
    for(int i = 1; i <= m; i ++) hs[i] = hs[i - 1] * P + s[i];

    hp[0] = 1;
    for(int i = 1; i <= n; i ++) hp[i] = hp[i - 1] * P;

    for(int l = 1; l <= m - n + 1; l ++)
    {
        int r = l + n - 1;
        if(QAQ(l, r) == hap) cout << l - 1 << " ";
    }

    return 0;

}