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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
sanya3271
0 / 0 / 0
Регистрация: 28.04.2012
Сообщений: 15
#1

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

13.08.2013, 19:36. Просмотров 347. Ответов 4
Метки нет (Все метки)

Суть такая, вводим 2 строки, программа должна найти максимальную подстроку из двух строк...
Пример
leybar //1 строка
hey //2ая

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

Нужен просто совет, чем руководствоваться при решении такого круга задач? Я нашел в инете такой интересный метод, как Суффиксный автомат...есть ли его аналоги? или ссылки, где эта тема более внятно объясняется?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.08.2013, 19:36     Поиск подстроки в двух строках
Посмотрите здесь:

C++ Поиск подстроки в строке
C++ Поиск подстроки
Поиск подстроки C++
Поиск подстроки C++
Поиск подстроки C++
C++ В двух строках найти подстроки и наибольшую подстроку
C++ Поиск подстроки
Поиск подстроки C++
C++ Поиск подстроки
Поиск подстроки C++
Поиск подстроки в строке C++
Поиск подстроки в строке C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
813 / 571 / 110
Регистрация: 28.07.2012
Сообщений: 1,522
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 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru