Алгоритм Рабина-Карпа (Реализация на C++)

C++   7 января 2012  Автор статьи:  

Нам нужно проверить, входит ли данная строка в данный текст, и если входит, то начиная с какого символа текста.

Входные данные:

Имеется некий текст Т(до 40000 символов) и образец S,на вхождение которого мы проверяем текст(до 10000 символов).Предполагаем,что вхождение существует.

Выходные данные:

На выводе будет сообщение о том,что образец был найден и с какого символа начинается вхождение образца S в текст T.

Реализация решения

#include
using namespace std;
int main()
{
char T[40000],S[10000];
int j,n,m,v=0,w=0,k=1,P = 9941,D=256;
/*
Ввод текста и образца
*/
for(int i=1;i<=m;i++) { v=(v*D+(int)S[i])%P; w=(w*D+(int)T[i])%P; } for(int i=1;i<=m-1;i++) k=(k*D)%P;//k имеет значение остатка деления Dm-1 на P
for(int i=m+1;i<=n+1;i++) { if(w==v){j=0;//если числа равны, то строки принадлежат одному классу, и надо проверить совпадают ли они while((j

  • Ruslan

    а чему равны то n и m а то компилятор ругается

  • Lordrp

    n равен размеру текста, m — размер образца. Для лучшего понимания прочитайте теорию.

  • Lordrp

    n равен размеру текста, m — размер образца. Для лучшего понимания прочитайте теорию.

  • Иван

    Так а куда текст то вводить и подстроку?

    • Массив T — это текст, а массив S — это подстрока. Когда читаете какую — то реализацию лучше загляните сначала в теорию, так как информация по самому алгоритму находится там, а тут в чем особенности реализации на C++ и сам код.

  • aleksey2093

    int main()

    {

    char T[40000] = «wagbvawydcuawbapplegovbawkeljhigswcnxi», S[10000]=»apple»;

    int i,j, n=39, m=6, v = 0, w = 0, k = 1, P = 9941, D = 256;

    puts(T);

    puts(S);

    for (int i = 1; i <= m; i++)

    {

    v = (v*D + (int)S[i]) % P;

    w = (w*D + (int)T[i]) % P;

    }

    for (int i = 1; i <= m — 1; i++)

    k = (k*D) % P;//k имеет значение остатка деления Dm-1 на P

    for (int i = m + 1; i <= n + 1; i++)

    {

    if (w == v){

    j = 0;//если числа равны, то строки принадлежат одному классу, и надо проверить совпадают ли они

    while ((j<m)&(S[j + 1] == T[i — m + j])){ j++; }

    if (j == m) cout << "Образец входит в текст начиная с" << i — m << "-го символа";//окончательная проверка

    }

    if (i <= n) w = (D*(w + P — (((int)T[i — m])*k) % P)) + (((int)T[i]) % P);

    }

    system("pause");

    return 0;

    }

    Ето не работает

    • Конец кода, конечно, испортился, но начало точно правильное. Пришли мне на почту lordrp@bk.ru(если все еще актуально)

  • Anastasia

    Переменные P и D: для чего они?

Научиться программировать

  • на Delphi

  • на Java

  • на C++