НП или нет?Поиск слова в существующем словаре, окруженном гибберишем - PullRequest
Новая
       10

НП или нет?Поиск слова в существующем словаре, окруженном гибберишем

0 голосов
/ 26 июня 2018

Итак, у нас с другом есть вопрос, на который мы не можем найти ответ.

Учитывая строку неизвестной длины или размера, покрытую библейской нотой, слово МОЖЕТ быть написано с ошибкой одним или двумя символами.Можно ли понять, каким должно быть это слово?

Пример: у нас есть словарь ['apple', 'banana', 'potato]

можно ли найти погоду или нет, любое из этих слов есть в строке, которая выглядит как-токак это:

alxcsfapple saodpjkasf (или это может быть неправильно написано, как это amncbxanana

он думает, что единственный способ сделать это n! Однако мы могли бы оптимизировать это, используя форму автозамены, которая предполагаетначало нового слова после каждой буквы в сочетании с три в не n! способ? Это проблема NP?

1 Ответ

0 голосов
/ 26 июня 2018

Этот поиск может быть выполнен за O(len(hay) * len(needle)) время с использованием модифицированного расстояния Левенштейна метрики, а именно: нулевая строка для сена должна быть инициализирована нулями (что означает, что мы можем начать с любой позициисено бесплатно).Так что это не NP.

Подробнее см. https://en.wikipedia.org/wiki/Approximate_string_matching#Problem_formulation_and_algorithms и http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/.

...