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

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

Восстановить пароль Регистрация
 
Clipper_701
0 / 0 / 0
Регистрация: 26.02.2013
Сообщений: 20
26.05.2014, 12:26     Поиск подстроки (Кнут-Моррис-Пратт) #1
Добрый день! Начал реализацию КМП

Текст задачи: В первой строке входного файла 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(своя, встроенная).
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
26.05.2014, 18:00     Поиск подстроки (Кнут-Моррис-Пратт) #2
почитай e-maxx
Clipper_701
0 / 0 / 0
Регистрация: 26.02.2013
Сообщений: 20
26.05.2014, 19:19  [ТС]     Поиск подстроки (Кнут-Моррис-Пратт) #3
А вобще можно решить без динамического массива и указателей? На e-maxx, есть готовая формула для нахождения префикс ф-ций, только дальше не ясно что с ней делать.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
26.05.2014, 19:46     Поиск подстроки (Кнут-Моррис-Пратт) #4
Там описан алгоритм КМП и даже есть док-во, насколько я помню. Алгоритм требует памяти пропорционально суммарной длине двух данных строк. Это всегда приемлимо. Я не знаю детерминированного оптимального по времени алгоритма, который требовал бы меньше памяти.
Yandex
Объявления
26.05.2014, 19:46     Поиск подстроки (Кнут-Моррис-Пратт)
Ответ Создать тему
Опции темы

Текущее время: 06:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru