@Mercury13
Программист на «си с крестами» и не только

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

Существуют форматы и протоколы (PHP, C++11, MIME и другие), где есть т.н. «неэкранированный» формат строк. Чтобы узнать, где конец строки, ищем особый маркер.
$s = <<<QQQ
SELECT x FROM y
WHERE z = 1;
QQQ;

А теперь предположим, что этот код делается автоматически. Как алгоритмически найти какое-нибудь QQQ, которого заведомо нет в строке? Желательно достаточно короткое, состоящее из заданного множества символов (например, больших букв) и за O(n).
  • Вопрос задан
  • 207 просмотров
Решения вопроса 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. Находим в маске ноль — это и есть нужный нам маркер.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы