Проблема в алгоритме поиска подстроки в строке [C++]

Question

Я написал этот алгоритм но почему-то не работает на тесте

aac ac

Пожалуйста подскажите где моя ошибка? Вот мой код:

int find(string str, string sub) {
    int i = 0, j = 0;
    while (j < str.size()) {
        int k = 0;
        while (j < sub.size()) {
            if (str[i] == sub[j]) {
                j++;
                i++;
                k++;
            } else {
                i++;
                k = 0;
                j = 0;
            }
        }
        
        if (k == sub.size()) {
            return i-k;
        }
    }
    return -1;
 }

Answer 1

Я изучаю алгоритм Кнута-Морриса-Пратта поэтому хочу написать свой скрипт

Ну, тогда примерно так:

int KMP_find(const string& in, const string& sub)
{
    vector<int> f(sub.size(),0);
    for(int t = 0, s = 1; s < f.size(); s++)
    {
        while((t > 0) && (sub[s] != sub[t]) ) t = f[t-1];
        if (sub[s] == sub[t]) f[s] = ++t; else f[s] = 0;
    };
    for(int s = 0, i = 0; i < in.size(); i++)
    {
        while((s > 0) && (in[i] != sub[s])) s = f[s-1];
        if (in[i] == sub[s]) s++;
        if (s == sub.size()) return i-s+1;
    };
    return -1;
};

То, что написали вы, никакого отношения к КМП не имеет - это попытка простого поиска путем "прикладывания" шаблона ко всем местам в строке и сравнения...

P.S. Только вот все равно find будет быстрее :)

БЛОГ НА HUSL

Проблема в алгоритме поиска подстроки в строке [C++]

Ответы (1 шт):