Создать самую короткую НЕ подстроку для данной строки

Question

Я работаю над кодом генерации сообщений MIME и хотел бы создать как можно меньшие границы для любого заданного ввода даже неизвестной длины в потоковом режиме.

Прямо сейчас я получаю достаточно хорошее решение на основе генератора случайных чисел. В основном я генерирую случайную строку из 32 символов Base64 и пытаюсь найти в ней самую короткую подстроку, которая не является подстрокой тела сообщения MIME.

Это не идеальное решение, потому что:

1. Граница не всегда самая короткая. Для очень упрощенного примера: для альфа-текста граница может быть только одной цифрой, но сгенерированный материал границы может содержать только альфы.

2. Мне нужен генератор случайных чисел и уникальное семя для него каждый раз, когда я запускаю приложение. В идеале лучше иметь детерминированный алгоритм.

Вот что я хочу знать. Можно ли сохранить свойство алгоритма потоковой передачи, работать с фиксированным объемом памяти, быть детерминированным и генерировать идеальную кратчайшую границу? Или мы можем достичь только некоторых свойств путем компромиссов?

Answer 1

Все границы начинаются с -- и находятся на отдельной строке. Вы можете использовать это, чтобы создать список всех возможных "похожих на границы" слов в теле, а затем создать уникальное слово для использования (например, лексикографически).

Кроме того, предполагая, что у вас менее 26 деталей, вы можете просто использовать отдельные буквы, если вы хотите "максимально короткие" границы. В этом случае сканирование может быть выполнено с помощью регулярного выражения:

^--([a-z])$

Это (в многострочном контексте) будет соответствовать всем однобуквенным "контекстоподобным" токенам в теле письма.

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

('a'...'z').where(!tokenHashSet.contains)

Все вышеперечисленное в псевдокоде, надеюсь, это понятно.