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

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

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

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

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

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

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

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

В двух строках найти подстроки и наибольшую подстроку - C++
char *beg_a , *beg_b; char a = "Father is strong"; char b = "In math give bool str"; char temp; int end_a,end_b,i; ...

Мне надо сделать поиск последнего вхождения подстроки s1 в строку s(с функцией LastPos, не strstr). В этом коде просто вхождение подстроки в строку. - C++
#include <stdio.h> int count_of_substrings(string s, string s1){ int start = 0; int count = 0; int pos = 0; ...

Поиск подстроки - C++
Эта программа написана чтобы искало буквы....а как написать чтобы искало количество слова например " kag " #include<iostream.h> ...

Поиск подстроки - C++
Всем привет. Вот такое вот дали задание: найти все вхождения данного образца в строке. При этом надо указать индекс в тексте с которого...

Поиск подстроки - C++
Привет всем. Я пишу программу для поиска подстроки. Если подстрока есть в строке, вывести YES. Иначе - NO. Вот код(еще не дописанный) ...

Поиск подстроки - C++
Народец))) Подскажите пожалуйста новичку,как найти подстроку в строке?

4
Belfegor
Ghost
173 / 173 / 6
Регистрация: 16.09.2012
Сообщений: 526
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
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
14.08.2013, 07:52 #3
Цитата Сообщение от sanya3271 Посмотреть сообщение
Суффиксный автомат
не надо браться за такие вещи на таком этапе...
у вашей задачи есть хорошее решение за O(N2) динамикой. уверен, что оно легко гуглится.

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

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

для >2 чтобы сделать, я так понял нужно склеивать строки и разделять какими-то символами
0
14.08.2013, 12:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2013, 12:03
Привет! Вот еще темы с ответами:

Поиск подстроки - C++
Подскажите, как в тексте типа этого - "101011110101001001001111010101010101100110", найти определенную комбинацию...

Поиск подстроки - C++
Всем добрый день, подскажите хорошая ли идея искать наличие подстроки таким способом, 8 строка. #include <iostream> #include <string> ...

Поиск подстроки - C++
Почему при поиске вхождения подстроки в строку если я ввожу несколько слов, то компилятор разделяет строку на слова и ищет вхождение в них?...

Поиск подстроки - C++
Как считать из файла поочерёдно подстроку и искать её в строке? И почему то в итоге не корректно выводится результат 2 -х значений. Вот...


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

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

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