Задать вопрос
@Mercury13
Программист на «си с крестами» и не только
алгоритмы

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

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

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

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

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
С developer (алгоритмист)
СберТех • Москва
от 350 000 ₽
Бэкенд программист
Grade Factor • Москва
от 80 000 ₽
С++ developer
TQB - хай-тек рекрутмент по-хардкору • Москва
от 300 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Скопировать верстку, посадить на функционал
20 апр. 2024, в 12:01
20000 руб./за проект
Разработать сайт-визитку на Wordpress
20 апр. 2024, в 11:52
5000 руб./за проект
Написать программу иммитирующую поведение человека для выбора услуг
20 апр. 2024, в 11:21
1000 руб./за проект
Ещё заказы