Uz
0 / 0 / 1
Регистрация: 05.07.2012
Сообщений: 23
1

Реализация алгоритма Рабина-Карпа для двух однонаправленных линейных списков

08.07.2012, 11:42. Показов 1809. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте! Собственно, вопрос находится в заголовке: у меня описано два списка, надо этим алгоритмом найти количество вхождений первого списка во второй. Прошу о помощи, заранее спасибо.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.07.2012, 11:42
Ответы с готовыми решениями:

Сравнение элементов двух однонаправленных линейных списков
А как сравнить элементы двух списков? Чтобы при совпадении элементов счётчик прибавлял единичку?...

Организовать представление множеств в виде линейных однонаправленных списков
Даны два множества А и В. Организовать представление множеств в виде линейных однонаправленных...

Как из двух однонаправленных списков создать третий, который состоит из нечетных элементов предыдущих двух?
ребят,подскажите пожалуйста как из двух однонаправленных списка создать третий который состоит из...

Из двух однонаправленных списков сформировать новый список
Из двух однонаправленных списков сформировать новый список, следующим образом: сначала записать...

1
Uz
0 / 0 / 1
Регистрация: 05.07.2012
Сообщений: 23
09.07.2012, 17:39  [ТС] 2
Лучший ответ Сообщение было отмечено Uz как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
string s, t; // входные данные
 
// считаем все степени p
const int p = 31;
vector<long long> p_pow (max (s.length(), t.length()));
p_pow[0] = 1;
for (size_t i=1; i<p_pow.size(); ++i)
    p_pow[i] = p_pow[i-1] * p;
 
// считаем хэши от всех префиксов строки T
vector<long long> h (t.length());
for (size_t i=0; i<t.length(); ++i)
{
    h[i] = (t[i] - 'a' + 1) * p_pow[i];
    if (i)  h[i] += h[i-1];
}
 
// считаем хэш от строки S
long long h_s = 0;
for (size_t i=0; i<s.length(); ++i)
    h_s += (s[i] - 'a' + 1) * p_pow[i];
 
// перебираем все подстроки T длины |S| и сравниваем их
for (size_t i = 0; i + s.length() - 1 < t.length(); ++i)
{
    long long cur_h = h[i+s.length()-1];
    if (i)  cur_h -= h[i-1];
    // приводим хэши к одной степени и сравниваем
    if (cur_h == h_s * p_pow[i])
        cout << i << ' ';
}
Как вот то же самое, только для двух однонаправленных списков реализовать? Помогите, пожалуйста.
0
09.07.2012, 17:39
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.07.2012, 17:39
Помогаю со студенческими работами здесь

Алгоритм Рабина-Карпа
Всем доброго времени суток! Имеется код Алгоритма Рабина-Карпа, поиск подстроки в строке. Сегодня...

Алгоритм Рабина-Карпа, нужны комментарии к коду
Привет всем. Столкнулся с задачей разобраться с кодом алгоритма рабина карпа. Объясните пожалуйста...

Усовершенствовать алгоритм Рабина-Карпа, чтобы он искал символьную подматрицу в символьной матрице
У меня есть этот алгоритм. Кто знает, как усовершенствовать его, чтобы он искал символьную...

Реализация теста Рабина-Миллера для чисел порядка 2^512
Необходимо реализовать тест для таких вот БОЛЬШИХ чисел. Но с арифметикой больших чисел на C\C++ не...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru