c++ - 查找子字符串出现的次数

Question

我有一个小问题。我正在解决一项编程任务，但遇到了问题。这是一个简单的，但时间限制使它变得有点困难。

Find number of occurrences of substring. You will be given M - length of substring; substring to find, N - length of base string; base string.
M <= 100 000
N<= 200 000

Input

10
budsvabbud
79
uaahskuskamikrofonubudsvabbudnebudlabutkspkspkspmusimriesitbudsvabbudsvabbudnel

Output
3

我尝试使用内置函数查找，但速度不够快:

#include<iostream>
#include<string>

using namespace std;

int main()
{
    int n;
    int occurrences = 0;
    string::size_type start = 0;
    string base_string, to_find;
    cin >> n >> to_find >> n >> base_string;
    while ((start = base_string.find(to_find, start)) != string::npos) {
        ++occurrences;
        start++;; // see the note
    }
    cout << occurrences << endl;
}

所以我尝试自己写一个函数，但是速度更慢:

#include<iostream>
#include<cstdio>
#include<string>
#include<queue>

using namespace std;

int main()
{
    int n, m;
    string to_find;
    queue<int> rada;  
    int occurrences = 0;
    cin >> m >> to_find >> n;
    for (int i = 0; i < n; i++)
    {
        char c;
        scanf(" %c", &c);
        int max = rada.size();
        for (int j = 0; j < max; j++)
        {
            int index = rada.front();
            rada.pop();
            if (c == to_find[index])  
            {
                if (++index == m) {
                    occurrences++;
                }
                else
                    rada.push(index);
            }
        }
        if (c == to_find[0])
        {
            if (1 == m)
                n++;
            else
                rada.push(1);
        }
    }
    cout << occurrences << endl;

}

我知道有些人在 0 毫秒内完成了这项工作，但我的第一个代码需要超过 2000 毫秒，而第二个代码比这要多得多。你有什么想法如何解决这个问题吗？ 谢谢。

编辑: 长度限制:

M <= 100 000 - 子字符串的长度

N<= 200 000 - 基本字符串的长度

Answer 1

您提供的算法是 O(M*N)，其中 N 是文本的长度，M 是搜索到的世界的长度。通常，库也会实现朴素算法。然而，Knuth、Morrison 和 Pratt 有一个算法，它在 O(M+N) 时间内完成。参见，例如，维基百科 Knuth-Morrison-Pratt Algorithm .它有一些变体可能更容易实现，例如 Boyer-Moore-Horsepool .