Форум программистов, компьютерный форум CyberForum.ru

Поиск подстроки в двух строках - C++

Восстановить пароль Регистрация
 
sanya3271
0 / 0 / 0
Регистрация: 28.04.2012
Сообщений: 15
13.08.2013, 19:36     Поиск подстроки в двух строках #1
Суть такая, вводим 2 строки, программа должна найти максимальную подстроку из двух строк...
Пример
leybar //1 строка
hey //2ая

ey//макс.подстрока в двух строках

Нужен просто совет, чем руководствоваться при решении такого круга задач? Я нашел в инете такой интересный метод, как Суффиксный автомат...есть ли его аналоги? или ссылки, где эта тема более внятно объясняется?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Belfegor
Ghost
 Аватар для Belfegor
172 / 172 / 6
Регистрация: 16.09.2012
Сообщений: 524
13.08.2013, 19:43     Поиск подстроки в двух строках #2
http://habrahabr.ru/post/113266/
http://habrahabr.ru/post/111449/
http://algolist.manual.ru/search/esearch/ - наилучшее
http://www.slideshare.net/grebenshikov/16-e
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
14.08.2013, 07:52     Поиск подстроки в двух строках #3
Цитата Сообщение от sanya3271 Посмотреть сообщение
Суффиксный автомат
не надо браться за такие вещи на таком этапе...
у вашей задачи есть хорошее решение за O(N2) динамикой. уверен, что оно легко гуглится.

Добавлено через 40 минут
да, гуглится не очень. напишите, если будут проблемы. насколько мне известно, лучше чем динамика, эту задачу решают только суф. структуры. но, повторюсь, вам рано.
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
14.08.2013, 09:53     Поиск подстроки в двух строках #4
Belfegor, судя из задачи тут не совсем поиск подстроки в строке. Задача состоит в нахождении наибольшей общей подстроки, а это уже другие алгоритмы.
sanya3271, советую искать решение на англ гугля longest common substring (не спутай с longest common subsequence).
sanya3271
0 / 0 / 0
Регистрация: 28.04.2012
Сообщений: 15
14.08.2013, 12:03  [ТС]     Поиск подстроки в двух строках #5
lcs искал уже)

Добавлено через 9 минут
сделал суффикс для 2ух строк, все работает
также нашел рабочий "наивный метод", который в вики расписан, тоже для 2ух работает

для >2 чтобы сделать, я так понял нужно склеивать строки и разделять какими-то символами
Yandex
Объявления
14.08.2013, 12:03     Поиск подстроки в двух строках
Ответ Создать тему
Опции темы

Текущее время: 02:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru