Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
VilDara
5 / 5 / 0
Регистрация: 27.08.2012
Сообщений: 153
1

Алгоритм нахождения наибольшей общей подстроки

01.06.2013, 20:11. Просмотров 870. Ответов 3
Метки нет (Все метки)

Например, у меня 3 строки:

alerroraa
marerrordd
nierrorasd

По какому алгоритму определить error и вынести его?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.06.2013, 20:11
Ответы с готовыми решениями:

Алгоритмы поиска наибольшей общей подстроки (LCS)
Заданы две строки: A и B. Их длины соответственно N и M. Найти максимальную общую подстроку двух...

Нахождение наибольшей общей подстроки!
/* Найти наибольшую общую подстроку у всех строк. Всего k строк(1<=k<=10). В каждой строке не...

Задача поиска наибольшей общей подстроки
Нужно написать вот эту программку на Си. Поясню допустим дано 2 строки из них нужно найти...

Алгоритм поиска максимальной общей подстроки
Доброго времени суток. Подскажите, как можно реализовать наиболее простой алгоритм поиска...

Алгоритм для нахождения последнего вхождения подстроки в строке
Ребята, устраиваюсь в крупную фирму, уже успешно прошел 2 технических собеседования, но просят ещё...

3
IyD
0 / 0 / 0
Регистрация: 29.05.2013
Сообщений: 2
02.06.2013, 11:42 2
У нас тут будет 4 цикла.
i. Пробегаемся по количеству символов (1 символ сопадает, 2, и т. д.). Как только мы определим, что n символов не совпали, то прерываем цикл и ответом будет n-1 символов.
i от 1 до длинны первой строки.
j. Пробегаем по символам первой строки. Если j достигло макс значения, а совпадений при данном i не было найдено, выходим из цикла j. И результатом будет i-1.
j от 1 до (длинны первой строки - i).
k. Пробегаем по количеству строк. Если цикл k завершён (мы не выходили из него досрочно), то выход из цикла j и запоминание в результат подстроки (j,j+i-1) первой строки.
k от 2 до количества всех строк.
l. Пробегаем по символам k-ой строки.
l от 1 до (длинны k-ой строки - i)
Проверяем совпадают ли подстроки (j,j+i-1) и (l,l+i-1) соответственно 1-ой и k-ой строк. Если есть совпадение, выходим из цикла l. Если нет совпадения и l приняло максимальное значение, то выходим из цикла k.

В качестве "первой" строки берём самую короткую по длине.
0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
02.06.2013, 22:20 3
VilDara, суффиксные структуры с этим справляются.Копайте в сторону суффиксного автомата
0
NurlashKO
89 / 89 / 80
Регистрация: 07.10.2012
Сообщений: 145
05.06.2013, 13:09 4
Можно еще Хешами и бин поиском по длинне подстроки... всего за O(k * len(s) * log(s)). Где к-количество строк, s - длинны строк.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2013, 13:09

Нужна реализация итерационного алгоритма наибольшей общей подпоследовательности
Или я нуб в гугле, или реализации этого алгоритма на паскале в сети нет. Мне нужен именно...

Задача поиска наибольщей общей подстроки
Нужно написать вот эту программку на Си. Поясню допустим дано 2 строки из них нужно найти...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru