Поиск неподстроки
Дан текст/строка/набор байт. Требуется найти такую строку, которая не является подстрокой этого текста. "Неподстрока" не должна быть слишком длинной, алгоритм поиска не должен быть слишком накладным.
Зачем это нужно? Скажем у вас есть текст, вы хотите вставить его heredoc. Вам нужны ограничители, которых вы не встретите в тексте.
Или вы хотите поменять в тексте символы местами с помощью replace. text.replace('a', 'b').replace('b', 'a') работать не будет. Нужно text.replace('a', T).replace('b', 'a').replace(T, 'b'), где T не встречается в исходном тексте, иначе будет плохо. (к T есть дополнительные требования, их пока опустим).
Или с помощью "неподстроки" можно вносить в текст разметку, которую затем можно удалить восстановив исходный текст. Применений много.
Ответы (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"
Не исключаю, что возможен тонкий момент - добавленная уникальная строка при замене чего-то там породит такую же с наложением, но навскидку примера я не сочинил.
Для текста или строки наименее характерным будет многократное повторение символа. Поэтому нужно сделать небольшую последовательность повторяющихся символов и проверить текст на наличие такой последовательности. Если нашлась, то добавить символы или изменить символ. Если не с первой попытки, то очень быстро искомая уникальная последовательность будет найдена. Для массива байтов может понадобиться чуть больше попыток. Помимо повторяющихся символов можно использовать упорядоченные последовательности.