Skip to content

14242: 【原4242】寻找子串

题目

题目描述

author: 铂金圣斗士 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4242

Description

给定一个字符串A和一个字符串B,求B在A中的出现次数。A和B中的字符均为英语大写字母或小写字母。

A中不同位置出现的B可重叠。

Input Format

输入共两行,分别是字符串A和字符串B。

Output Format

一个整数,表示B在A中的出现次数。

Sample Input

zyzyzyz
zyz

Sample Output

3

Subtasks

  • 对于30%的数据, 满足存在一定随机性。

  • 对于100%的数据, 满足\(1\leqA, B的长度\leq 10^6\), A、B仅包含大小写字母。

ligongzzz's solution

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

using ull = unsigned long long;

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

    string A, B;
    cin >> A >> B;

    if (A.length() < B.length()) {
        cout << 0;
        return 0;
    }
    int al = A.length(), bl = B.length();

    ull hasha = 0, hashb = 0, pnum = 1ull;
    for (int i = 0; i < bl; ++i) {
        hasha = hasha * 131ull + ull(A[i]);
        hashb = hashb * 131ull + ull(B[i]);
        pnum *= 131ull;
    }

    int cnt = 0;
    for (int i = 0;; ++i) {
        if (hasha == hashb)
            ++cnt;
        if (i + bl >= al)
            break;

        hasha = hasha * 131ull + ull(A[i + bl]) - pnum * ull(A[i]);
    }

    cout << cnt;

    return 0;
}