少了确认那一步多出几个

一段文本 abababcababcabababc（19 个字符，下标从 0 起）和一个模式 ababc。

把一段字符折成一个数：h = (h × 31 + 字母序号) % 17，a 记 1、b 记 2、c 记 3。

左边是逐字符比出来的个数，右边是只比哈希、不做确认的个数：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const string T = "abababcababcabababc";
const string P = "ababc";

vector<int> brute(const string& t, const string& p) {
    vector<int> pos;
    for (int i = 0; i + (int)p.size() <= (int)t.size(); i++) {
        if (t.compare(i, p.size(), p) == 0) pos.push_back(i);
    }
    return pos;
}

const int BASE = 31;
const int MOD = 17;

int hs(const string& s) {
    int h = 0;
    for (char c : s) h = (h * BASE + (c - 'a' + 1)) % MOD;
    return h;
}

vector<int> hash_only(const string& t, const string& p) {
    vector<int> pos;
    int hp = hs(p);
    for (int i = 0; i + (int)p.size() <= (int)t.size(); i++) {
        if (hs(t.substr(i, p.size())) == hp) pos.push_back(i);
    }
    return pos;
}

int main() {
    cout << brute(T, P).size() << "/" << hash_only(T, P).size() << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）