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

@Advin · Регистрация: 12.12.2013

Author24 — интернет-сервис помощи студентам

нужно с помощью алгоритма КМП найти первое вхождение одной числовой последовательности в другую ... не сроки! спасибо

@~~IrineK~~ · 02.04.2014, 07:21

Сообщение от Advin

не сроки!

В смысле "не строки"?

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

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

C

int seek_substring_KMP (char s[], char p[])
{ 
    int i, j, N, M; 
    N = strlen(s); 
    M = strlen(p);

На такой:

C

int seek_substring_KMP (int s[], int p[])
{ 
    int i, j, N, M; 
    N = sizeof(s) / sizeof(int); 
    M = sizeof (p) / sizeof(int);

А дальше - все по тексту.

@ZaMaZaN4iK · 02.04.2014, 08:19

Advin, если вам дана сама последовательность, то что Вам мешает запихнуть её в строку, а потом посчитать префикс-функцию и использовать её значение?

C++

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 заранее рассчитать
}

@Advin · 02.04.2014, 21:34 **[ТС]**

я вектор еще не учил мне нужно так дана числовая последовательность типа НЕ char...и найти первое вхождение одной числовой последовательности в другую

Новые блоги и статьи
Как написать микросервис на C# с Kafka, MediatR, Redis и GitLab CI/CD InfoMaster 15.01.2025 В современной разработке программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот подход позволяет разделить сложную систему. . .	Что такое CQRS и как это реализовать на C# с MediatR InfoMaster 15.01.2025 Концепция CQRS и её роль в современной разработке В современном мире разработки программного обеспечения архитектурные паттерны играют ключевую роль в создании масштабируемых и поддерживаемых. . .	Как настроить CI/CD с Azure DevOps InfoMaster 15.01.2025 CI/ CD, или непрерывная интеграция и непрерывное развертывание, представляет собой современный подход к разработке программного обеспечения, который позволяет автоматизировать и оптимизировать процесс. . .	Как настроить CI/CD с помощью Jenkins InfoMaster 15.01.2025 Введение в CI/ CD и Jenkins В современной разработке программного обеспечения непрерывная интеграция (CI) и непрерывная доставка (CD) стали неотъемлемыми элементами процесса создания качественных. . .	Как написать микросервис на Go/Golang с Kafka, REST и GitHub CI/CD InfoMaster 14.01.2025 Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .	Как написать микросервис с нуля на C# с RabbitMQ, CQRS, Swagger и CI/CD InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .
Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .	Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .	Как создать игру "Танчики" на Unity3d и C# InfoMaster 14.01.2025 Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .	Организую платный онлайн микро-курс по доработке Android-клиента Telegram _Ivana 14.01.2025 Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента! 4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве). Первое вводное занятие. . .	Как создать приложение для фитнеса для iOS/iPhone на Kotlin InfoMaster 14.01.2025 Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .	Как создать приложение магазина для iOS/iPhone на Swift InfoMaster 14.01.2025 Введение в разработку iOS-приложений Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .

@Advin 0 / 0 / 0 Регистрация: 12.12.2013 Сообщений: 13
		1
	Алгоритм КМП(Кнута-Морриса-Пратта ) 01.04.2014, 23:04. Показов 7635. Ответов 3 Метки нет (Все метки) нужно с помощью алгоритма КМП найти первое вхождение одной числовой последовательности в другую ... не сроки! спасибо 0

@Advin 0 / 0 / 0 Регистрация: 12.12.2013 Сообщений: 13
	02.04.2014, 21:34 [ТС]	4
	я вектор еще не учил мне нужно так дана числовая последовательность типа НЕ char...и найти первое вхождение одной числовой последовательности в другую 0

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

Решение