Как удалить все повторяющиеся слова и буквы строки?

Я пытаюсь удалить каждый символ, повторяющийся более 2 раз, из очень длинной строки. Так, например, слово Terrrrrrific становится Terrific.

Теперь мой вопрос: как мне отфильтровать повторы, которые включают более одного символа, то есть, если у меня есть Words words words words words, я хочу отфильтровать его до words words, однако это может быть что-то менее разумное, например abcdabcdabcdabcdabcd, которое должно стать abcdabcd.

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


string algorithm suffix-tree
person Daniel Rusznyak    schedule 30.06.2015    source источник
comment
То, что вы ищете, также известно как тандемные повторы (из-за родственной задачи, связанной с последовательностями ДНК). Когда вы разрешаете использовать более одного символа, вы должны тщательно определить, что вы подразумеваете под повтором: например. words words words words words также содержит 3 (перекрывающихся) повтора строки words words words.   -  person j_random_hacker    schedule 30.06.2015

Ответы (1)


arrow_upward
0
arrow_downward

Я не знаю, является ли этот алгоритм эффективным для вас, но вы можете сделать это:

  1. Выберите длину для поиска повторов
  2. Затем для каждой начальной точки от 0 до длины-1 пройти через строку
  3. Поддерживать стек (вы используете непересекающиеся подстроки и помещаете их в стек, если два верхних элемента стека отличаются от них)
person encrypt    schedule 30.06.2015