Описание тега knuth-morris-pratt
Алгоритм Кнута – Морриса – Пратта - это эффективный алгоритм сопоставления строк.
1
ответ
Функция префикса KMP DFA
Меня попросили узнать о KMP DFA, и то, что я нашел в своей книге, - это реализация, но наш лектор все время вызывает что-то "префиксную функцию". Я действительно не могу понять, какая часть этой функции здесь, кто-то может мне это объяснить? Извинит…
24 ноя '13 в 00:23
1
ответ
Проблема в реализации алгоритма Кнута Морриса Пратта
Я пытаюсь реализовать алгоритм Кнута Морриса Пратта для поиска по шаблону в Java, но он не дает никакого результата. Код генератора prefixTable работает нормально, как я его проверил, но основной код для поиска не работает public void KMPAlgorithm(S…
23 ноя '15 в 17:08
4
ответа
Соответствие строковому шаблону с одним или нулевым несоответствием
Учитывая строку и образец, который нужно сопоставить, насколько эффективно могут быть найдены совпадения, имеющие ноль или одно несоответствие. e.g) S = abbbaaabbbabab P = abab Matches are abbb(index 0),aaab(index 4),abbb(index 6),abab(index 10) Я п…
12 апр '12 в 09:40
1
ответ
Алгоритм быстрого поиска строк для больших строк
Я пытаюсь реализовать программное обеспечение для обнаружения плагиата, используя алгоритмы сопоставления с образцом. Здесь я наткнулся на алгоритм KMP и опробовал реализацию C#. Я вижу, что это не так быстро для реальных документов (не для строк, я…
23 май '17 в 22:09
1
ответ
Макс нет раз конкретный символ в строке в алгоритме Кнута Морриса Пратта сравнивается со строкой?
Позволять T:String P:pattern Каково максимальное число случаев, когда конкретный символ в строке (T) в алгоритме Кнута Морриса Пратта сравнивается с шаблоном (P)?
19 апр '15 в 20:43
2
ответа
Стол Кнут-Моррис-Пратт Фэйл
Я готовлюсь к экзамену и изучаю алгоритм Кнута-Морриса-Пратта. То, что будет на экзамене - это таблица ошибок и конструкция DFA. Я понимаю конструкцию DFA, но не совсем понимаю, как составить таблицу ошибок. Если у меня есть пример шаблона "abababc"…
24 апр '14 в 05:59
1
ответ
Почему мы не сдвигаемся в этом направлении?
При изучении алгоритма Кнута – Морриса – Пратта для строки: ABC ABCDAB ABCDAB для шаблона: ABCDABD Я застрял на одном шаге. Я выделю шаг, на котором я сейчас застрял. ABC ABCDAB ABCDAB ABCDABD ABC ABCDAB ABCDAB ABCDABD ABC ABCDAB ABCDAB ABCDABD ABC …
01 ноя '12 в 12:28
0
ответов
Использует ли std::string::find() KMP или дерево суффиксов?
Интересно, какой алгоритм используется для сопоставления шаблона со строкой в стандартной библиотеке. Суффиксное дерево было бы лучшим выбором, если бы у вас было больше поиска для выполнения в пределах одной строки. Это структура данных за std::s…
12 мар '18 в 17:44
2
ответа
Расчет функции отказа КМП
Мой профессор решил функцию отказа KMP следующим образом: index 1 2 3 4 5 6 7 8 9 string a a b a a b a b b ff 0 1 2 1 2 3 4 5 1 Из других текстов, которые я проверил онлайн, я обнаружил, что это может быть неправильно, я вернулся, чтобы подтвердить …
20 апр '13 в 21:49
4
ответа
Сравнение строк в Java, какой алгоритм мне использовать?
У меня есть требование сравнить название продукта, который пользователь будет искать, с доступными продуктами. У меня есть название продуктов, хранящихся в базе данных MySQL. Я собираю все имена и получаю их на уровне приложения (java) один раз, ког…
25 ноя '13 в 06:49
1
ответ
Реализация Кнута-Морриса-Пратта в Хаскеле - Индекс за пределами
Я использовал псевдокод из Википедии в попытке написать алгоритм KMP на Haskell. Это дает "индекс вне границ", когда я пытаюсь найти за пределами длины шаблона, и я не могу найти проблему; мои "исправления" только испортили результат. import Control…
14 янв '16 в 22:33
1
ответ
Построение DFA в алгоритме Кнута-Морриса-Пратта
Я имею в виду схему алгоритма Кнута-Морриса-Пратта (KMP) для поиска подстрок в книге Седжвика "Алгоритмы" (4-е изд.). Алгоритм KMP использует резервную копию в поиске подстроки на основе детерминированного конечного автомата (DFA). Я понимаю, как DF…
30 май '15 в 15:52
1
ответ
Хвостовой рекурсивный алгоритм Кнута – Морриса – Пратта
Я создал простую реализацию алгоритма Кнута-Морриса-Пратта в Scala. Теперь я хочу стать фантазером и сделать то же самое в хвостовой рекурсии. Мое инстинктивное чувство говорит, что это не должно быть слишком сложно (как для таблицы, так и для поиск…
26 май '14 в 05:54
1
ответ
Время выполнения алгоритма KMP и построения таблицы LPS
Недавно я наткнулся на алгоритм KMP и потратил много времени, пытаясь понять, почему он работает. Хотя сейчас я понимаю основные функциональные возможности, я просто не могу понять вычисления во время выполнения. Я взял приведенный ниже код с сайта …
30 окт '18 в 20:29
1
ответ
Результирующий "count" строки "pattern" в не полученной печати. вот код
Я попытался реализовать алгоритм Кнута Морриса Пратта. результирующий вид рисунка в тексте не печатается. Переменная count содержит значение того, сколько раз шаблон появлялся в строке. Пожалуйста, помогите решить проблему package main import "fmt" …
03 авг '18 в 09:46
0
ответов
Вычисление следующего префиксного индекса в реализациях KMP
Я прочитал несколько различных реализаций KMP и не могу понять один аспект, который они все разделяют. Когда они вычисляют самый длинный префикс, который также является суффикс-массивом (lps). Если символы не совпадают в индексах, протестированных н…
13 фев '17 в 08:34
3
ответа
Строка поиска Java (км)
Я хочу найти, сколько вхождений строки (скажем, a) в строке b. Я думал о реализации алгоритма Кнута-Морриса-Пратта, но я предпочитаю встроенную функцию Java. Есть ли такая функция? Я хочу, чтобы функция была как можно более низкой, насколько это воз…
14 апр '12 в 18:06
1
ответ
Алгоритм Кнута-Морриса-Пратта в Хаскеле
У меня проблемы с пониманием этой реализации алгоритма Кнута-Морриса-Пратта в Haskell. http://twanvl.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell В частности, я не понимаю конструкцию автомата. Я знаю, что он использует метод "Связывание узла" для …
22 май '13 в 14:21
1
ответ
Какова функция для алгоритма сбоя KMP?
Какие правильные функции сообщают нам таблицу сбоев KMP? Я смотрел на пару, но они очень сбивают с толку. Я немного запутался с суффиксами и префиксами и как их сопоставить? Я считаю, что мы начнем с -1 а также 0 но я не могу понять остальную часть …
09 июн '15 в 07:38
1
ответ
Реализация Кнута-Морриса-Пратта в чистом C
У меня есть следующая KMP-реализация: #include <stdio.h> #include <stdlib.h> #include <string.h> int kmp(char substr[], char str[]) { int i, j, N, M; N = strlen(str); M = strlen(substr); int *d = (int*)malloc(M * sizeof(int)); d[0]…
29 июн '12 в 07:17