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

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

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

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

26.05.2014, 12:26. Просмотров 568. Ответов 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(своя, встроенная).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2014, 12:26     Поиск подстроки (Кнут-Моррис-Пратт)
Посмотрите здесь:

C++ Поиск подстроки
Мне надо сделать поиск последнего вхождения подстроки s1 в строку s(с функцией LastPos, не strstr). В этом коде просто вхождение подстроки в строку. C++
Поиск подстроки C++
C++ Поиск подстроки в строке
C++ Поиск подстроки в строке
Поиск подстроки C++
Поиск подстроки C++
C++ Поиск подстроки
Поиск подстроки C++
C++ Поиск подстроки
Поиск подстроки C++
Поиск подстроки в строке C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
26.05.2014, 18:00     Поиск подстроки (Кнут-Моррис-Пратт) #2
почитай e-maxx
Clipper_701
0 / 0 / 0
Регистрация: 26.02.2013
Сообщений: 21
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     Поиск подстроки (Кнут-Моррис-Пратт)
Ответ Создать тему
Опции темы

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