Создайте кратчайшую НЕ подстроку для заданной строки

Question

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

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

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

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

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

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

Answer 1

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

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

^--([a-z])$ 

Это (в многострочном контексте) будет соответствовать всем одна букве «контекстным как» маркеры в теле сообщения электронной почты.

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

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

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