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

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

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

Поиск подстроки (Кнут-Моррис-Пратт) - C++

26.05.2014, 12:26. Просмотров 639. Ответов 3
Метки нет (Все метки)

Добрый день! Начал реализацию КМП

Текст задачи: В первой строке входного файла INPUT.TXT записана строка S, во второй строке записана строка T. Обе строки состоят только из латинских букв. Длины строк больше 0 и меньше 50 000.

Входные данные:
ababbababa
aba

Вывод:
0 5 7

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include<string>
using namespace std;
 
 
//Функция substring, в задаче нельзя пользоваться встроенной ф-цией substring, написал свою.
 
string su(string s2,int start,int end)
{
string ans="";
for(int i=start;i<end;i+=1)
{
    ans+=s2[i];
}
return ans;
}
 
 
int main()
{
 
 
 
 
 
 
 
 
 
string s4="ababbababa"; //исходная строка s4
string s5="aba";// подстрока s5
 
for(int i2=0;i2<s4.length();i2++) 
{
    
string s3=su(s4,i2,s4.length()); //вывод ababbababa, babbababa, abbababa, bbababa, bababa, ababa, baba, aba,
ba,a. Все сдвиги хранятся в s3
 
 
string s4=su(s3,0,s5.length()); //т.к. нужно сравнить, если первые символы до длины s5, равны самой s5, то вхождение найдено.
if(s4==s5)
{
    cout<<" "<<i2; //вывод 0 5 7, т.е. первый символ s4 - 'a', если в сумме от этого символа до длины s5, получится s5, то выводим его индекс. 
}
 
}
}
Проблема в том что до первого теста, на отправке выводится time limit exceeded(превышение времени работы), можно ли вобще решить КМП, не используя динамичный массив, указатели или префикс функцию?
Получается что даже, нельзя будет использовать своу ф-цию substring, но тогда как можно будет сравнивать подстроку с строкой при сдвиге? Заранее спасибо!

Добавлено через 2 часа 33 минуты
Если все таки нужно решать, с помощью префикс функций, то где можно посмотреть как ее посчитать вручную, пока не особо ясно с чего подступить к КМП, по идее логика решения выше правильная, но мне хотелось бы узнать как можно решить КМП без ф-ции substring(своя, встроенная).
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2014, 12:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск подстроки (Кнут-Моррис-Пратт) (C++):

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

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

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

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

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

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

3
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
26.05.2014, 18:00 #2
почитай e-maxx
0
Clipper_701
0 / 0 / 0
Регистрация: 26.02.2013
Сообщений: 21
26.05.2014, 19:19  [ТС] #3
А вобще можно решить без динамического массива и указателей? На e-maxx, есть готовая формула для нахождения префикс ф-ций, только дальше не ясно что с ней делать.
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
26.05.2014, 19:46 #4
Там описан алгоритм КМП и даже есть док-во, насколько я помню. Алгоритм требует памяти пропорционально суммарной длине двух данных строк. Это всегда приемлимо. Я не знаю детерминированного оптимального по времени алгоритма, который требовал бы меньше памяти.
0
26.05.2014, 19:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.05.2014, 19:46
Привет! Вот еще темы с ответами:

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

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

Поиск подстроки - C++
Эта программа написана чтобы искало буквы....а как написать чтобы искало количество слова например &quot; kag &quot; #include&lt;iostream.h&gt; ...

Поиск подстроки в строке - C++
Здравствуйте. Очень нужна программа поиска подстроки в строке. Действительно оч нужна. точная формулировка задачи: Написать...


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

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

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