How much Horspool reads

string matching precomputation measurement

Before putting a search algorithm into your program, you want to know how much work it will do on your data, not on someone else's benchmark. Count this for Horspool's algorithm, the simplified Boyer–Moore that fast searches in standard libraries rest on.

A text t of length n, a pattern p of length m. A window is a place where the pattern is laid against the text; the first window starts at position 0. In the window starting at s the algorithm compares p[m − 1] with t[s + m − 1], then p[m − 2] with t[s + m − 2], and so on from right to left while the letters are equal; each check of a pair of letters is one comparison. If all m letters match, it is an occurrence. Then, matched or not, the window shifts by d(c), where c = t[s + m − 1] is the text letter under the last cell of the window:

if c occurs among the first m − 1 letters of the pattern, d(c) = m − 1 − j, where j is the rightmost such position;
if it does not, d(c) = m.

The algorithm stops when the window no longer fits in the text. For each pattern print how many windows it checked, how many comparisons it made and how many occurrences it found. Among the tests are the beginning of “War and Peace” in Russian and in the Maude translation, the genome of phage lambda, and the example from Moore's paper, “HERE IS A SIMPLE EXAMPLE”.

Input

The first line is the text, 1 to 100,000 characters (UTF-8, no line breaks; spaces are ordinary characters). The second is the number of patterns q (1 ≤ q ≤ 20). Each of the next q lines is a pattern of 1 to 100 characters. Positions are counted in characters, not bytes. The tests are such that each takes fewer than a million comparisons.

Output

For each pattern, a line of three numbers: windows, comparisons, occurrences.

Examples

Example 1

Input

HERE IS A SIMPLE EXAMPLE
3
EXAMPLE
SIMPLE
E

Output

5 15 1
5 14 1
24 24 5

Example 2

Input

abracadabra abracadabra
3
abra
cad
zzz

Output

7 19 4
9 13 2
7 7 0

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 8 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

This is a simulation, not a clever way of finding an answer: the answer is the run of the algorithm. All that remains is to carry it out exactly as stated and to find d(c) quickly.

2Hint 2

Build the shift table once per pattern: go through the first m − 1 letters from left to right and write d[p[j]] = m − 1 − j. Rightmost occurrences overwrite leftmost ones. What would go wrong if you went through all m letters?

3The idea

The last letter of the pattern is not in the table. It already stands under the last cell of the window; if it were in the table, its shift would be 0, and a window ending in that letter would never move. What is needed is the previous copy of that letter in the pattern: it gives the right shift.

4Walkthrough

The table is a dictionary “letter → shift” over the first m − 1 letters, m by default. Then a loop over windows: comparisons from right to left up to the first mismatch, counting, and a shift by the letter under the last cell.

Look at the answers. On “War and Peace” Horspool makes about one comparison per window, and the longer the pattern, the fewer windows: for «князь Василий» (“Prince Vasili”) about 6000 windows per 60,000 characters. The one-letter pattern «а» checks every position, like the naive search. And in the seventh test the pattern “b” followed by nineteen “a” on a text of nothing but “a” makes almost 400,000 comparisons per 20,000 characters: each window compares 19 matching letters, trips over the “b” and shifts by one position, because there is an “a” under the last cell again. The naive search is twenty times faster here: it starts comparing with the “b”.

4+Solution

5Complexity

The table is O(m). The search is O(n · m) in the worst case, as in the seventh test, and about n/m windows on ordinary text with a large alphabet.

6Common mistakes

A table over all m letters. The last letter gets a shift of 0, which is “fixed” to 1, and windows ending in that letter crawl one position at a time. On “SIMPLE” in the first sample this gives six windows instead of five.
Shifting by the mismatched letter. That is the Boyer–Moore rule, not Horspool's: in Horspool the shift is always computed from the letter under the last cell of the window, even if the mismatch happened further left.
Bytes instead of characters. In UTF-8 a Cyrillic letter is two bytes, and there will be more windows and comparisons. Read strings as characters (in Go, []rune).

Algorithms behind it

STR Algorithm Boyer–Moore Compares from right to left and skips letters: on long patterns it reads only a small part of the text. O(n + m) 2 problems