Member 12898564 Ответов: 2

Напишите функцию, правильно реализующую алгоритм Рабина карпа


Мне поручено написать функцию, которая реализует алгоритм Рабина карпа с одним текстом и массивом списка возможных паттернов. Шаблон представляет собой массив из k указателей, а длина текста равна m. Результат не прошел предусмотренную тестовую функцию. Я не могу понять, в чем ошибка. Может ли кто-нибудь сказать мне, где находятся ошибки или как я могу написать другую тестовую функцию, чтобы увидеть, что я возвращаю здесь, чтобы я мог сравнить ее с правильной?

Что я уже пробовал:

  int substring(char * text, int k, int m, char* patterns[])
{   
    int hp = 0; // hash value of pattern
    int t = 0; // hash value of text
    int h = 0; 
    int i , j;
    int p = 1009; //prime number > 1000
    int d = 256; // random base of polynomial
    text[200];
    char pat[100];

    for (i = 0; i < k - 1; i++)
        h = (h*d) % p;

    //hash value of pattern and hash value of the compared text substring
    for (i = 0; i < k; i++)
    {
        hp = (d*p + pat[i]) % p;
        t = (d*p + text[i]) % p;
    }

    //slide pattern over text
    for (i = 0; i <= m - k; i++)
    {
        if (hp == t)
        {
            for (j = 0; j < k; j++)
            {
                if (text[i+j] != patterns[j])
                    break;
            }
            if (j == k)
                return i;
        }

        if (i < m - k)
        {
            t = (d*(t - text[i] * h) + text[i+k]) % p;

            if (t < 0)
                t = (t + p);
        }
    }

}

[no name]

В дополнение к решению 1, Не входите в привычку использовать односимвольные имена переменных. Вы можете вспомнить, для чего сегодня была использована буква "н", но на следующей неделе вы этого не сделаете. Если "p" - простое число, то сделайте переменную именем primeNumber, и вам не придется пытаться вспомнить, что это такое, и вам не нужно будет иметь дополнительный комментарий, чтобы напомнить вам, что это такое.

2 Ответов

Рейтинг:
2

Patrice T

Цитата:
Результат не прошел предусмотренную тестовую функцию. Я не могу понять, в чем ошибка.

Это ваш код, вы должны знать, как он работает с отладчиком, видеть, как он делает свое дело, и проверять, соответствует ли он вашим ожиданиям.

Вы должны научиться использовать отладчик как можно скорее. Вместо того чтобы гадать, что делает ваш код, пришло время увидеть, как он выполняется, и убедиться, что он делает то, что вы ожидаете.

Отладчик-Википедия, свободная энциклопедия[^]
Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]

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


Рейтинг:
1

OriginalGriff

Нет, это часть задания: заставить его работать!
Используйте отладчик и начните смотреть на то, что происходит во время выполнения кода.
Я не могу быть явным-я понятия не имею, какую систему вы используете, поэтому я не могу сказать вам, что такое команды отладчика, но Google скажет вам, если вы спросите - поставьте точку останова в начале функции, и отладчик остановится, когда достигнет ее. Затем вы можете посмотреть на содержимое переменных и одноступенчатые линии, чтобы увидеть, какой эффект они оказывают и куда идет поток.
Попробуйте перед выполнением каждой строки определить, чего вы ожидаете, и сравнить это с тем, что произошло. Если они не совпадают, почему бы и нет?

Попробуйте: вы написали код, чтобы знать, чего вы от него ожидаете - самое интересное-заставить его делать именно то, что вы хотели! :Д


Member 12898564

Я не научился использовать отладчик во время выполнения, я знаю только, как отлаживать во время компиляции. Я решил, что моя ошибка заключается в том, что я не назначил свой массив параметров указателя char* patterns[] в функцию. Как я могу его назначить?

OriginalGriff

Вы не можете отлаживать во время компиляции: отладка-это процесс удаления ошибок из запущенного программного обеспечения. Прежде чем он сможет работать, вы должны исправить синтаксические ошибки, что является частью процесса компиляции.
Google "отладчик" и имя компилятора или системы, которую вы используете, и вы должны получить много информации о том, как его использовать. Не "разбирайтесь в этом" - используйте отладчик и узнайте!