Поиск неподстроки

Рейтинг: 2Ответов: 1Опубликовано: 03.02.2023

Дан текст/строка/набор байт. Требуется найти такую строку, которая не является подстрокой этого текста. "Неподстрока" не должна быть слишком длинной, алгоритм поиска не должен быть слишком накладным.

Зачем это нужно? Скажем у вас есть текст, вы хотите вставить его heredoc. Вам нужны ограничители, которых вы не встретите в тексте.

Или вы хотите поменять в тексте символы местами с помощью replace. text.replace('a', 'b').replace('b', 'a') работать не будет. Нужно text.replace('a', T).replace('b', 'a').replace(T, 'b'), где T не встречается в исходном тексте, иначе будет плохо. (к T есть дополнительные требования, их пока опустим).

Или с помощью "неподстроки" можно вносить в текст разметку, которую затем можно удалить восстановив исходный текст. Применений много.

строки алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 2

Простой случай - когда в строке задействованы не все символы из доступного набора, тогда берём не встречающийся в строке символ.

Иначе строим суффиксный массив. Это массив номеров, под которыми идут суффиксы в лексикографическом порядке. Например, для строки "ababab" суффиксы

       pos   order
ababab  0      2 
 babab  1      5 
  abab  2      1
   bab  3      4
    ab  4      0
     b  5      3

Считаем длины наибольших общих префиксов соседних (по номерам в массиве) суффиксов - LCP, longest common prefix - например, с помощью алгоритма Касаи.

       pos   order   lcp
    ab  4      0     
  abab  2      1      2 
ababab  0      2      4 
     b  5      3      0 
   bab  3      4      1 
 babab  1      5      3

Выбираем пару соседних суффиксов с небольшим значением LCP[i] и строим строку между ними ababab, b => "aa"

Не исключаю, что возможен тонкий момент - добавленная уникальная строка при замене чего-то там породит такую же с наложением, но навскидку примера я не сочинил.