0

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

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;
 }
2
  • Вы оба цикла while сделали с одной переменной j, например. Но главное - если уж вы работаете с string, то почему бы просто не воспользоваться готовой find для этого типа? И еще - почему бы не передавать строки как константные ссылки, чтобы избежать лишнего копирования?
    – Harry
    3 мар 2021 в 4:01
  • Спасибо. Я изучаю алгоритм Кнута-Морриса-Пратта поэтому хочу написать свой скрипт
    – MaJS
    3 мар 2021 в 6:33

1 ответ 1

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 будет быстрее :)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.