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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Изменение даты файла на предыдущий день http://www.cyberforum.ru/cpp-beginners/thread1188295.html
Помогите разобраться, вопрос следующий: каждый день выгружается архив, я разархивирую его утром изменяю некоторые значения, и мне каждый раз приходится изменять дату на самом файле, и изменять дату на архиве., вы не подскажете: как можно это автоматизировать?(дата должна быть сегодня - 1сутки, время всегда 23.45.02) нашел код: (но это не совсем то что нужно) SYSTEMTIME lf; FILETIME...
C++ Вывести на экран изображения множества разноцветных кругов (случайные размеры и заполнения) до нажатия любой к Вывести на экран изображения множества разноцветных кругов (случайные размеры и заполнения) до нажатия любой клавиши. http://www.cyberforum.ru/cpp-beginners/thread1188278.html
Составить программу, позволяющую получить словесное описание школьных отметок C++
Задачи довольно простые. Я проста не разбираюсь в этом языке программирование. Проста срочно нужны решение. Думаю дальнейшем его изучить)Заранее спасибо. Задача 2. Составить программу, позволяющую получить словесное описание школьных отметок. Например, 1 – «очень плохо», 2 – «неудовлетворительно», …., 5 – «отлично»
C++ Конструктор по умолчанию
Показывает ошибку : 1 IntelliSense: для класса "tovar" не существует конструктор по умолчанию Подскажите пожалуйста как сделать #pragma once class tovar { public: char *name; char *type;
C++ Исправить ошибку "Expected unqualified-id before '{' token" http://www.cyberforum.ru/cpp-beginners/thread1188233.html
#include <stdio.h> #include <string.h> #include <ctype.h> using namespace std; #define MAX 10 #define EMPTY -1
C++ Считать из текстового файла только определенные строки считать из текстового файла например строки с 6 по 9, или с 3 по 19 и записать их в другой текстовый файл подробнее

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

Текст задачи: В первой строке входного файла 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(своя, встроенная).
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 16:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru