Lesson_06/Task_3/Task_3.cpp - master - AirLexa/03

Lesson_06/Task_3/Task_3.cpp
48 строк2 KB
AirLexa
загрузил Lesson_06/Task_3/Task_3.cpp
20 янв 2026, 22:40
20 янв 2026, 22:40ea0e286
#include <iostream>
#include <string>
#include <windows.h>

int find_substring_light_rabin_karp(std::string &source, std::string &substring)
{
    int sub_hash = 0;
    for (char c : substring) sub_hash += c; // считаем хеш подстроки
    int hash = 0;
    int len_sub = substring.length();
    for (int i = 0; i < source.length() - len_sub; i++)
    {
        if (i == 0) // если только начали, то считаем хеш от 0 до длины подстроки
            for (int j = 0; j < len_sub; j++)
                hash += source[j];
        else // иначе прибавляем новый крайний символ и отнимаем бывший первый
            hash += source[i + len_sub - 1] - source[i - 1];

        if (hash != sub_hash) continue; // хеш не совпал идем на следующий символ
        bool check_ok = true; // надеемся что будет совпадение посимвольно
        for (int n = 0; n < len_sub && check_ok; n++) // проверяем посимвольно, ведь хеши совпали
            if (source[i + n] != substring[n]) check_ok = false; // нет, не равны символы, прерываем цикл
        if (check_ok) return i;
    }
    return -1;
}

int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    std::string source = "";
    std::cout << "Введите строку, в которой будет осуществляться поиск: ";
    getline(std::cin, source);
    std::string sub = "";
    while (sub != "exit")
    {
        std::cout << "Введите подстроку, которую нужно найти: ";
        getline(std::cin, sub);
        int i = find_substring_light_rabin_karp(source, sub);
        if (i < 0) std::cout << "Подстрока \"" << sub << "\" не найдена";
        else std::cout << "Подстрока \"" << sub << "\" найдена по индексу " << i;
        std::cout << std::endl;
    }
    std::cout << "До свидания! До новых встреч!" << std::endl;

    return 0;
}