The good suffix table

string matching precomputation contests

You are writing your own pattern search in the manner of grep, with the Boyer–Moore algorithm. The bad character table is simple to build. The second one, the good suffix table, is harder: it is needed when the end of the pattern has already matched the text and the next letter has not. Patterns can be long, up to a hundred thousand characters, and the table must be built quickly.

A pattern p of length m, positions from zero. Suppose the window was compared from right to left, the letters p[i + 1..m − 1] matched the text, and p[i] did not. What is known about the text under the window: on the right, the same letters as p[i + 1..m − 1], and under position i a letter not equal to p[i]. A shift s (1 ≤ s ≤ m) does not contradict this if

p[k − s] = p[k] for all k from i + 1 to m − 1 with k − s ≥ 0;
and, if i − s ≥ 0, then p[i − s] ≠ p[i].

Positions that end up left of the start of the pattern after the shift are not constrained. The value gs[i] is the smallest such shift. The shift m always fits. For each pattern print the whole table gs[0], …, gs[m − 1].

For the pattern AT-THAT from Boyer and Moore's 1977 paper the table is 5 5 5 5 5 3 1: if “T” matched but the “A” before it did not, the window shifts by 3, so that the “T” from the middle of the pattern, preceded by “-” rather than “A”, comes under the matched “T”. Among the tests are phrases from “War and Peace”, a telomere, pieces of the phage lambda genome, Fibonacci words and Thue–Morse words.

Input

The first line holds the number of patterns q (1 ≤ q ≤ 1000). Each of the next q lines is a pattern: a non-empty UTF-8 string without line breaks, spaces being ordinary characters. The total length of the patterns is at most 100,000 characters; lengths and positions are counted in characters, not bytes.

Output

For each pattern, a line of m numbers separated by spaces: gs[0], …, gs[m − 1].

Examples

Example 1

Input

2
AT-THAT
EXAMPLE

Output

5 5 5 5 5 3 1
6 6 6 6 6 6 1

Example 2

Input

3
abracadabra
колокол
aaaa

Output

7 7 7 7 7 7 7 10 10 3 1
4 4 4 4 7 7 1
1 2 3 4

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 10 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

The definition can be checked head-on for every pair (i, s), but that is O(m²) pairs plus comparisons inside. You need a way to tell in O(1) how far the end of the pattern matches the piece ending at position t.

2Hint 2

Let suff[t] be the length of the longest common end of p[0..t] and the whole p. This is the Z-function of the reversed pattern read backwards: suff[t] = z_rev[m − 1 − t].

3Hint 3

A shift s fits position i in two cases. Either the copy of the matched end lies wholly within the pattern and is preceded by a different letter: suff[m − 1 − s] equals exactly m − 1 − i. Or the copy sticks out past the left edge: then p[0..m − 1 − s] is both a beginning and an end of the pattern, suff[m − 1 − s] = m − s, and s ≥ i + 1.

4The idea

Each candidate s of the first case serves exactly one position i = m − 1 − suff[m − 1 − s]. So all such shifts are placed in one pass over t = m − 1 − s: go from left to right, and for each position the rightmost copy, that is, the smallest shift, remains. The second case is the borders of the pattern: the shift to the longest border that fits left of a position fills all i to its left.

5Walkthrough

Three passes: the Z-function of the reversed pattern gives suff; a pass over the borders from the longest fills gs with shifts of the second case; a pass over t from left to right overwrites them with shifts of the first case, which are always smaller. This is the same procedure as in the article's listing; Gusfield calls it Boyer–Moore on the Z-function.

Look at the second sample. For “aaaa” the table is 1 2 3 4: if the last k letters “a” matched and the text has something other than “a” before them, the window has to step over that letter entirely; any smaller shift puts an “a” under it. A weak rule that forgets the mismatched letter gives 1 everywhere and on a text of nothing but “a” turns Boyer–Moore into the naive search.

5+Solution

6Complexity

O(m) per pattern: the Z-function and two passes. Going through pairs (i, s) with a check via suff is O(m²): on a pattern of a hundred thousand characters that is ten billion steps.

7Common mistakes

The weak rule. A shift is checked only for matching the end, without the condition p[i − s] ≠ p[i]. The shifts stay safe but are shorter than needed: for «колокол» (“bell”), when «ол» matched and the «к» before it did not, the weak rule gives 4 and puts a «к» under the mismatched text letter again; the right answer is 7.
Forgetting the borders. If the matched end occurs nowhere else in the pattern in full, the shift is not always m: the beginning of the pattern may match the tail of that end. For “abracadabra”, when “bra” matched and the “a” before it did not, the copy of “bra” at the start will not do (it is also preceded by “a”), yet the shift is still 10, not 11: the first letter of the pattern matches the last letter of the matched end.
Bytes instead of characters. The table is built over letters: in Go, over []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