Поиск подстроки в строке и вывод элемента с которого начинается подстрока

Question

Задание: Дана строка и её подстрока. Найдите номер символа начала подстроки в первой строке.

Моя реализация:

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


int main() {
    string line;
    getline(cin, line);
    string subline;
    getline(cin, subline);
    bool fl = true;
    int cycle;
    int line_len = line.size();
    int sub_len = subline.size();
    for (int i = 0; i < line_len; i++) {
        if (subline[0] == line[i]) {
            fl = true;
            cycle = i;
            break;
        } else { fl = false; }
    }
    int count = 0;
    if (fl){
        for (int i = cycle + 1; i < line_len; i ++){
            if (subline[i] == line[i]){
                count += 1;
            }
            if (count == sub_len - 1){
                cout << cycle + 1;
                break;
            }
        }
    }
}

Проблема: Для входных данных вида:

abc ab Программа выводит верный ответ - 1, но для dabc abc не выводит ничего. Подскажите в чём ошибка моей реализации.

UPD: Использование готовых методов запрещено.

Answer 1

Ну вообще-то ошибок достаточно. У вашей - во втором цикле вы ставите индекс равный номеру символа в первой строке но в оба массива. line[i] - правильно, а subline[i] - неправильно, должно быть с начала строки. И проверять нужно до конца подстроки, а не начальной строки.

for (int i = cycle + 1; i < line_len; i ++) // ошибка - проверка должна быть до конца подстроки
{
    if (subline[i] == line[i]) // ошибка - выход за пределы массива!!!
      {}

Кроме того, у вас архитектура алгоритма неправильная. В первом цикле ищется первая буква подстроки и потом цикл заканчивается. А во втором цикле сравниваются символы подстроки с начальной строкой. Так вот второй цикл должен быть вложен в первый, иначе вы пропустите часть результатов. Например исходная строка dafvbabc а найти нужно ab. Первый цикл найдет первую a - второй символ и остановится. Второй цикл проверит совпадение остальных символов подстроки, не найдет совпадения и выйдет. И программа закончится. А подстрока ab содержится дальше в исходной строке.
Алгоритм должен быть примерно таким:

цикл по исходной строке - поиск первого символа подстроки
если найден, начинаем двумя индексами (указателями, итераторами) параллельно двигаться по обеим строкам и сравниваем символы.
если дошли до конца подстроки и все символы совпали - подстрока найдена.
если символы не совпали - продолжаем двигаться по первому (внешнему) циклу

БЛОГ НА HUSL

Поиск подстроки в строке и вывод элемента с которого начинается подстрока

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