Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Clipper_701
0 / 0 / 1
Регистрация: 26.02.2013
Сообщений: 21
#1

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

26.05.2014, 12:26. Просмотров 675. Ответов 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(своя, встроенная).
http://www.cyberforum.ru/cpp-beginners/thread1201122.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2014, 12:26
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Поиск подстроки (Кнут-Моррис-Пратт) (C++):

Поиск подстроки
Эта программа написана чтобы искало буквы....а как написать чтобы искало...

Поиск подстроки
Почему при поиске вхождения подстроки в строку если я ввожу несколько слов, то...

Поиск подстроки
Всем добрый день, подскажите хорошая ли идея искать наличие подстроки таким...

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

Поиск подстроки
Подскажите, как в тексте типа этого -...

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

Поиск подстроки
Как считать из файла поочерёдно подстроку и искать её в строке? И почему то в...

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

Поиск вхождения подстроки
int AString::find(char* podstr) { if (strstr(str, podstr) != NULL) return...

Поиск подстроки в строке
Доброго времени суток! Столкнулся с такой задачей. Вводим 10 слов, далее вводим...


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

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

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