VPF::Реализация алгоритма Эль-Гамаля или Рабина

DrAcu1A

Дата 14.5.2008, 16:39 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 14.5.2008

Репутация: нет
Всего: нет

Пожалуйста помогите написать прогу для реализации алгоритма Эль-Гамаля или Алгоритма Рабина, желательно не очень мудрёную, чтоб в ней можно было разобраться

Sartorius

Дата 14.5.2008, 17:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37

Код


#include <stdio.h>
#include <math.h>
#include <string.h>

#define MAX_SUBSTR_LEN 10

long powerTable[MAX_SUBSTR_LEN] = {0};

void initPowerTable()
{
    for (int i = 0; i < MAX_SUBSTR_LEN; i++)
    {
        powerTable[i] = pow('z', i);
    }
}

long int hash(const char * str, unsigned int str_len)
{
    long result = 0;

    for (int i = 0; i < str_len; i++)
    {
        result += str[i] * powerTable[i];
    }

    return result;
}

int RabinKarp(const char * str, const char * substr)
{
    int i, j;

    long subh = hash(substr, strlen(substr));
    long sh = hash(str, strlen(substr));

    for (i = 0; i < strlen(str) - strlen(substr); i++)
    {
        if(subh == sh)
        {
            return i;
        }
        // calculate new hash
        sh /= 'z';
        sh += powerTable[strlen(substr) - 1] * str[i + strlen(substr) ];
    }

    return -1;
}

void main()
{
    initPowerTable();
    printf("%d", RabinKarp("AA    BLA AAA", "BLA"));
}

Уберите только эти бесконечные вызовы strlen() smile

) Ну и для слишком длинных подстрок, когда хэш становится вырожденным добавьте проверку strncmp() еще

Это сообщение отредактировал(а) Sartorius - 14.5.2008, 17:25

DrAcu1A

Дата 14.5.2008, 17:28 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 14.5.2008

Репутация: нет
Всего: нет

Спаисибо Огромное =)

Sartorius

Дата 14.5.2008, 17:32 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37

Хм. то что я написал из за переполнения ошибается на длинных подстроках
Здесь можно найти пример с другим хэшем:
http://algolist.manual.ru/search/esearch/karp_rab.php

DrAcu1A

Дата 14.5.2008, 18:30 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 14.5.2008

Репутация: нет
Всего: нет

хмм...прога запускаеться, но в ней что то не так, после запуска она сразу же выкидывает, а при нажатии Alt+F5 там просто стоит цифра 6

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »