Найти количество вхождений подстроки

Question

Найти количество вхождений подстроки

У меня небольшая проблема. Я решаю одну задачу программирования, но у меня есть проблема с ней. Это просто, но ограничение по времени делает его немного сложнее.

Найти количество вхождений подстроки. Вам дадут М — длину
подстроки; подстрока для поиска, N — длина базовой строки; база
строка.
M <= 100 000
N<= 200 000

вход

10
budsvabbud
79
uaahskuskamikrofonubudsvabbudnebudlabutkspkspkspmusimriesitbudsvabbudsvabbudнель

Выход
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 — длина базовой струны

0

c++find find-occurrences performance string

Решение

Другие решения

Я пытаюсь этот код в режиме отладки без какой-либо оптимизации, и это заняло 11 мсек. VS.NET 2013, Intel Core i7:

int main()
{
int n;
int occurrences = 0;
string::size_type start = 0;
string base_string, to_find;
base_string.reserve(200000);
to_find.reserve(100000);
for (size_t i = 0; i < 100000; i++){
base_string.push_back('a');
}
for (size_t i = 0; i < 100000; i++){
base_string.push_back('b');
}
for (size_t i = 0; i < 100000; i++){
to_find.push_back('b');
}
auto start_s = clock();
while ((start = base_string.find(to_find, start)) != string::npos) {
++occurrences;
start++;; // see the note
}
auto stop_s = clock();
std::cout << (stop_s - start_s) / double(CLOCKS_PER_SEC) * 1000;
cout << occurrences << endl;
std::getchar();
}

Существует проблема в компиляторе, конфигурации, вашей машине, но в вашем коде.

0

static size_t findOccurences(const char * const aInput, const char * const aDelim)
{
if (aInput == 0x0 || aDelim == 0x0)
{
throw std::runtime_error("Argument(s) null");
}

const size_t inputLength = strlen(aInput);
const size_t delimLength = strlen(aDelim);

size_t result = 0;

if (delimLength <= inputLength && delimLength > 0)
{
size_t delimIndex = 0;

for (size_t inputIndex = 0; inputIndex < inputLength; inputIndex++)
{
if (aInput[inputIndex] != aDelim[delimIndex])
{
delimIndex = 0;
}
else
{
delimIndex++;

if (delimIndex == delimLength)
{
delimIndex = 0;
result++;
}
}
}
}

return result;
}

static size_t unsafeFindOccurences(const char * const aInput, const char * const aDelim)
{
const size_t inputLength = strlen(aInput);
const size_t delimLength = strlen(aDelim);

size_t result = 0;
size_t delimIndex = 0;

for (size_t inputIndex = 0; inputIndex < inputLength; inputIndex++)
{
if (aInput[inputIndex] != aDelim[delimIndex])
{
delimIndex = 0;
}
else
{
delimIndex++;

if (delimIndex == delimLength)
{
delimIndex = 0;
result++;
}
}
}

return result;
}

          x86        x64
Debug     5501ms     5813ms
Release   3889ms     3998ms

          x86        x64
Debug     5442ms     5564ms
Release   3074ms     3139ms

Скомпилировано с Visual Studio 2015, набор инструментов Visual Studio 2015 (v140) под Windows 10 x64 Pro.

С помощью этот вход. Поиск по объявлению и 1.000.000 итераций.

0

Источник

Accepted Answer

Представленный вами алгоритм представляет собой O (M * N), где N — длина текста, а M — длина искомого мира. Обычно также библиотеки реализуют наивный алгоритм. Однако есть алгоритм Кнута, Моррисона и Пратта, который делает это за O (M + N) времени. Смотрите, например, Википедию Алгоритм Кнута-Моррисона-Пратта. Он имеет несколько вариантов, которые могут быть проще реализовать, как Бойер-Мур-Horsepool.

2