[数据结构与算法]POJ3461（KMP or 哈希）

Oulipo - POJ 3461 - Virtual Judge

记录p串在s串中出现了多少次

KMP版本AC代码：

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <cstdio>
#include <stdio.h>
#include <string.h>
using namespace std;

void solve() {
    string s, p;
    cin >> p >> s;
    int lenp = p.size();
    int lens = s.size();
    vector<int> next(lenp + 1);
    next[0] = -1;
    int j = 0, k = -1;
    while (j < lenp) {
        if (k == -1 || p[j] == p[k]) {
            j++;
            k++;
            if (p[j] == p[k]) {
                next[j] = next[k];
            }
            else {
                next[j] = k;
            }
        }
        else {
            k = next[k];
        }
    }
    int ans = 0;
    int i = 0;
    j = 0;
    while (i < lenp && j < lens) {
        if (i == -1 || p[i] == s[j]) {
            i++;
            j++;
        }
        else {
            i = next[i];
        }
        if (i == lenp) {
            ans++;
            i = next[i];
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

哈希版本AC代码：

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <cstdio>
#include <stdio.h>
#include <string.h>
using namespace std;

const int base = 31;
const int maxn = 1000010;
string s, p;
long long b[maxn];
long long hash1[maxn];

void solve() {
    cin >> p >> s;
    int lenp = p.size();
    int lens = s.size();
    long long ssum = 0;
    for (int i = lenp - 1; i >= 0; i--) {
        ssum = ssum * base + (p[i] - 'a' + 1);
    }
    hash1[lens] = 0;
    for (int i = lens - 1; i >= 0; i--) {
        hash1[i] = hash1[i + 1] * base + (s[i] - 'a' + 1);
    }
    int ans = 0;
    for (int i = 0; i <= lens - lenp; i++) {
        if (ssum == hash1[i] - hash1[i + lenp] * b[lenp]) {
            ans++;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int t;
    b[0] = 1;
    for (int i = 1; i < maxn; i++) {
        b[i] = b[i - 1] * base;
    }
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}