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

@sanya3271 · Регистрация: 28.04.2012

Студворк — интернет-сервис помощи студентам

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

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

Нужен просто совет, чем руководствоваться при решении такого круга задач? Я нашел в инете такой интересный метод, как Суффиксный автомат...есть ли его аналоги? или ссылки, где эта тема более внятно объясняется?

@Belfegor · 13.08.2013, 19:43

http://habrahabr.ru/post/113266/
http://habrahabr.ru/post/111449/
http://algolist.manual.ru/search/esearch/ - наилучшее
http://www.slideshare.net/grebenshikov/16-e

@salam · 14.08.2013, 07:52

Сообщение от sanya3271

Суффиксный автомат

не надо браться за такие вещи на таком этапе...
у вашей задачи есть хорошее решение за O(N²) динамикой. уверен, что оно легко гуглится.

Добавлено через 40 минут
да, гуглится не очень. напишите, если будут проблемы. насколько мне известно, лучше чем динамика, эту задачу решают только суф. структуры. но, повторюсь, вам рано.

@nonedark2008 · 14.08.2013, 09:53

Belfegor, судя из задачи тут не совсем поиск подстроки в строке. Задача состоит в нахождении наибольшей общей подстроки, а это уже другие алгоритмы.
sanya3271, советую искать решение на англ гугля longest common substring (не спутай с longest common subsequence).

@sanya3271 · 14.08.2013, 12:03 **[ТС]**

lcs искал уже)

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

для >2 чтобы сделать, я так понял нужно склеивать строки и разделять какими-то символами

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

@sanya3271 0 / 0 / 0 Регистрация: 28.04.2012 Сообщений: 15

	Поиск подстроки в двух строках 13.08.2013, 19:36. Показов 1545. Ответов 4 Метки нет (Все метки) Суть такая, вводим 2 строки, программа должна найти максимальную подстроку из двух строк... Пример leybar //1 строка hey //2ая ey//макс.подстрока в двух строках Нужен просто совет, чем руководствоваться при решении такого круга задач? Я нашел в инете такой интересный метод, как Суффиксный автомат...есть ли его аналоги? или ссылки, где эта тема более внятно объясняется? 0

@Belfegor Ghost 174 / 174 / 40 Регистрация: 16.09.2012 Сообщений: 526
	13.08.2013, 19:43
	http://habrahabr.ru/post/113266/ http://habrahabr.ru/post/111449/ http://algolist.manual.ru/search/esearch/ - наилучшее http://www.slideshare.net/grebenshikov/16-e 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	14.08.2013, 09:53
	Belfegor, судя из задачи тут не совсем поиск подстроки в строке. Задача состоит в нахождении наибольшей общей подстроки, а это уже другие алгоритмы. sanya3271, советую искать решение на англ гугля longest common substring (не спутай с longest common subsequence). 0

@sanya3271 0 / 0 / 0 Регистрация: 28.04.2012 Сообщений: 15
	14.08.2013, 12:03 [ТС]
	lcs искал уже) Добавлено через 9 минут сделал суффикс для 2ух строк, все работает также нашел рабочий "наивный метод", который в вики расписан, тоже для 2ух работает для >2 чтобы сделать, я так понял нужно склеивать строки и разделять какими-то символами 0