LINUX.ORG.RU

Алгоритм поиска повторений внутри строки

 


0

3

Хочу алгоритм, желательно дешёвый, который имея вот такую строку

Hello worworworworld. You are welcome welhello welsobaka

Сможет сказать, что таки да, в строке есть повторения («wor» и «wel» и «ello» и может что-то ещё; алгоритм который говорит где они и какие они — не особо нужен, хотя второстепенно интересно).

Основной смысл - говорить «true» на штуки вида. Плюс ещё жалетально задавать минимальную длину повторяющейся строки и число повторений.

asdf;ljasdf;lkjasdfl;jkasdf;lkjasdf

Я конечно придумаю сам, но вдруг чё есть готовое.


Хочу алгоритм, желательно дешёвый

Суффиксное дерево может сказать про повторения. Но вот насчет дешевизны непонятно, может есть что-то и дешевле

Deleted
()

вдруг чё есть готовое.

Алгоритмы на строках ©.

quickquest ★★★★★
()

В любой строке, содержащей больше символов, чем размер алфавита, есть хотя бы одно повторение длины 1. Тебе нужно уточнить, что ты хочешь.

Gvidon ★★★★
()
Ответ на: комментарий от Gvidon

Тебе нужно уточнить, что ты хочешь.

Это:

задавать минимальную длину повторяющейся строки и число повторений.

anonymous
()

Стандартное решение это словарь N-грамм.

строка: foofoo
словарь:
foo: [0, 3]
oof: [1]
ofo: [2]

urxvt ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.