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

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

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

Алгоритм КМП(Кнута-Морриса-Пратта ) - C++

01.04.2014, 23:04. Просмотров 1319. Ответов 3
Метки нет (Все метки)

нужно с помощью алгоритма КМП найти первое вхождение одной числовой последовательности в другую ... не сроки! спасибо
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.04.2014, 23:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм КМП(Кнута-Морриса-Пратта ) (C++):

Алгоритм Кнута, Морриса и Пратта - C++
//описание функции алгоритма Кнута, Морриса и Пратта int KMPSearch(char *string, char *substring){ int sl, ssl; int res = -1; ...

Алгоритм Кнута-Морриса-Пратта - C++
здравствуйте. можете объяснить по примеру алгоритм кнута-морриса-пратта

Алгоритм Кнута-Морриса-Пратта - C++
Здравствуйте. Есть задание в котором необходимо найти вхождения подстроки в строку.Пример входных и выходных данных: 1 2 3 4 2 3 ...

Алгоритм поиска по строке Кнута-Морриса-Пратта - C++
Само задание таково: Программа должна быть грамотно функционально разбита на модули и функции. • Входные данные – текстовый файл. ...

Поиск заданной подстроки в строке (алгоритм Кнута-Морриса-Пратта) - C++
Привет всем. Мне нужно написать программу поиска заданной подстроки в строке. Если подстрока есть - вывести YES. Если нет - NO. Задача...

Быстрый поиск подстроки в строке (Кнута-Морриса-Пратта) - C++
Всем здрасьте. Преподаватель дал задание, найти подстроку в строке. Я задание это выполнил. Он сказал что мой алгоритм будет работать...

3
IrineK
Заблокирован
02.04.2014, 07:21 #2
Цитата Сообщение от Advin Посмотреть сообщение
не сроки!
В смысле "не строки"?

Добавлено через 40 минут
Алгоритм КМП

Тот пример, который на Си легко преобразуется под числовой массив.
Меняем этот фрагмент:

C
1
2
3
4
5
int seek_substring_KMP (char s[], char p[])
{ 
    int i, j, N, M; 
    N = strlen(s); 
    M = strlen(p);
На такой:
C
1
2
3
4
5
int seek_substring_KMP (int s[], int p[])
{ 
    int i, j, N, M; 
    N = sizeof(s) / sizeof(int); 
    M = sizeof (p) / sizeof(int);
А дальше - все по тексту.
1
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
02.04.2014, 08:19 #3
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Advin, если вам дана сама последовательность, то что Вам мешает запихнуть её в строку, а потом посчитать префикс-функцию и использовать её значение?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void kmp(vector <int> &p)
{
    for(i=1;i<size;++i)
    {
        j=p[i-1];
        while(j>0 && s[i] != s[j])
            j=p[j-1];
        if(s[i] == s[j])
            ++j;
        p[i]=j;
    }
}
 
void search_in_str(vector<int> &p)//нахождение подстроки в строке
{
    s=s_pref+"$"+s_main;
    size=s.length();
    size_pref=s_pref.length();
    kmp(p);
    for(i=0;i<size;++i)
        if(p[i] == size_pref)
            cout<<i-2*size_pref;//2*size_pref заранее рассчитать
}
1
Advin
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 13
02.04.2014, 21:34  [ТС] #4
я вектор еще не учил мне нужно так дана числовая последовательность типа НЕ char...и найти первое вхождение одной числовой последовательности в другую
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.04.2014, 21:34
Привет! Вот еще темы с ответами:

Поиск подстроки в строке по алгоритму КМН (Кнута-Морриса-Пратта) - C++
Здравствуйте. Я к вам с вопросом: не могу справиться уже длительное время с лабораторной работой. Формулировка задания: Дано слово...

Алгоритм Кнутта-Морриса-Пратта. Как вывести на экран число вхождений? - C++
В интернете нашел алгоритм Кнутта-Морриса-Пратта. Там была предоставлена сама реализация алгоритма. Как вывести на экран число вхождений? ...

Пример из Пратта - C++
Немого модифицированный пример из Пратта. Для переменной snack2 при выводе cout-ом работает четко, при выводе через функцию output выносит...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...


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

Или воспользуйтесь поиском по форуму:
4
Yandex
Объявления
02.04.2014, 21:34
Ответ Создать тему
Опции темы

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