Как найти маркер конца текста?

Question

[Mercury13]

Существуют форматы и протоколы (PHP, C++11, MIME и другие), где есть т.н. «неэкранированный» формат строк. Чтобы узнать, где конец строки, ищем особый маркер.

$s = <<<QQQ
SELECT x FROM y
WHERE z = 1;
QQQ;

А теперь предположим, что этот код делается автоматически. Как алгоритмически найти какое-нибудь QQQ, которого заведомо нет в строке? Желательно достаточно короткое, состоящее из заданного множества символов (например, больших букв) и за O(n).

Comments

[Алексей Ярков]

Я правильно понимаю? Вам в строке типа

$s = <<<НЕИЗВЕСТНОСТЬ
SELECT x FROM y
WHERE z = 1;
НЕИЗВЕСТНОСТЬ;

надо найти НЕИЗВЕСТНОСТЬ?

[Mercury13]

Совершенно верно.

Answer 1

[Mercury13]

Придумал. Пусть Σ' — это наш алфавит, из которого можно делать маркеры.
1. Определяем макс. длину маркера — mlen = ceil( log{|Σ'|}(length + 1) ).
2. Заводим битовую маску длины |Σ'| + |Σ'|² + … + |Σ'|^{mlen−1} + length + 1.
Каждый возможный маркер обозначим числом:
A = 0, B = 1, …, Z = 25, AA = 26, AZ = 51, BA = 52…
3. Очередь пуста.
4. Если очередной символ из Σ' — смотрим, сколько символов сзади из Σ', и ставим единицы в соотв. позициях маски.
5. Находим в маске ноль — это и есть нужный нам маркер.