How to find the end of text marker?

Question

Algorithms

There are formats and protocols (PHP, C++11, MIME and others), where there is a so-called. "unescaped" string format. To find out where the end of the line is, look for a special marker.

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

Now suppose that this code is done automatically. How to algorithmically find some QQQ, which is obviously not in the string? Preferably short enough, consisting of a given set of characters (for example, capital letters) and in O(n).

Answer 1

Invented. Let Σ' be our alphabet from which markers can be made.
1. Determine the max. marker length — mlen = ceil( log{|Σ'|}(length + 1) ).
2. Set up a bitmask of length |Σ'| + |Σ'|² + … + |Σ'|^{mlen−1} + length + 1.
Denote each possible marker by a number:
A = 0, B = 1, …, Z = 25, AA = 26, AZ = 51, BA = 52…
3. The queue is empty.
4. If the next character is from Σ', we look at how many characters are behind from Σ', and set the units according to. mask positions.
5. We find zero in the mask - this is the marker we need.