почему не работает алгоритм Робина-Карпа?

Question

ввожу текст оно чего-то сразу пишет что совпадение не найдено или алгоритм Робина-Карпа ищет подстроку в тексте без пробелов?

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
using namespace std;

#define tonum(c) (c >= 'A' && c <= 'Z' ? c - 'A' : c - 'a' + 26)


int mod(int a, int p, int m)
{
    if (p == 0)
        return 1;
    int sqr = mod(a, p / 2, m) % m;

    if (p & 1)
        return ((a % m) * sqr) % m;
    else
        return sqr;
}

int RabinKarpMatch(char* T, char* P, int d, int q)
{
    int i, j, p, t, n, m, h, found;
    n = strlen(T);
    m = strlen(P);
    h = mod(d, m - 1, q);
    p = t = 0;

    for (i = 0; i < m; i++)
    {
        p = (d * p + tonum(P[i])) % q;
        t = (d * t + tonum(T[i])) % q;
    }

    for (i = 0; i <= n; i++)
    {
        if (p == t)
        {
            found = 1;
            for (j = 0; j < m; j++)
                if (P[j] != T[i + j])
                {
                    found = 0;
                    break;
                }
            if (found)
                return i + 1;
        }
        else
        {
            t = (d * (t - ((tonum(T[i]) * h) % q)) + tonum(T[i + m])) % q;
        }
    }
    return -1;
}

int main(int argc, char* argv[])
{
    int sovp;
    int d = 1, q = 1000;
    char T[200];
    char P[100];
    cout << "Vvedite text" << endl;
    cin >> T;
    cout << "Vvedite stroku" << endl;
    cin >> P;
    sovp = RabinKarpMatch(T, P, d, q);
    if (sovp)
        cout << "Slovo naideno v " << sovp << " posizii";
    else
        cout << "Sovpadenii ne naideno!!!";
    system("pause");
    return 0;
}

Answer 1

Вместо cin нужно использовать getline эта фунция позволяет принимать строки с пробелами. C помощью strcpy и метода строки c_str можно заполнить массив char

#include <cstdlib>

. . . 

int main(int argc, char* argv[])
{
    int sovp;
    int d = 1, q = 1000;
    char T[200];
    char P[100];
    string t;
    string p;
    cout << "Vvedite text" << endl;
    getline(cin, t);
    strcpy(T, t.c_str());
    cout << "Vvedite stroku" << endl;
    getline(cin, p);
    strcpy(P, p.c_str());
   
    sovp = RabinKarpMatch(T, P, d, q);
    if (sovp)
        cout << "Slovo naideno v " << sovp << " posizii";
    else
        cout << "Sovpadenii ne naideno!!!";
    system("pause");
    return 0;
}

БЛОГ НА HUSL

почему не работает алгоритм Робина-Карпа?

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