Question bank — Boyer-Moore — bad character, good suffix heuristics

False. On large alphabets it is often sublinear: a single mismatch near the pattern's end can force a jump of $m$, so whole runs of text are never inspected — that is the entire point.

True. When $\text{last}(c)\ge j$ the raw formula $j-\text{last}(c)$ is $\le 0$, a zero or backward shift; without the $\max (1,\cdot )$ clamp the alignment never advances.

False. Each rule is independently a safe lower bound — neither ever skips a match — so the larger of two safe shifts is still safe, just faster.

True. With $\text{last}(c)=-1$ the shift is $j-(-1)=j+1$, sliding $P[0]$ to just past the offending text char, because no alignment overlapping $c$ can ever match.

False. Right-to-left scanning is what produces a matched suffix; the good-suffix rule and the "rightmost bad char" logic both depend on knowing the suffix, not a prefix — reverse it and the skipping logic collapses.

False. Both are cheap. Good suffix exists because in adversarial cases (e.g. the bad char equals a late occurrence) bad-character shift degenerates to $1$; good suffix supplies the large legal jump there.

False. It shifts by $G[0]$, the good-suffix jump for the whole pattern — the width of the largest border tells you the next earliest place $P$ could reoccur, which is usually more than $1$.

False. $O(n/m)$ is the best case. Basic BM's worst case is $O(nm)$ (e.g. $P=\text{aaa}$, $T=\text{aaaa}\dots$); the Galil Rule repairs this to guaranteed $O(n)$.

True. The rightmost $c$ in $P$ may sit to the right of the mismatch index; that is exactly the "would move backward" case that the $\max (1,\cdot )$ clamp handles.

False. It guarantees a safe shift, but Case 1 may only slide $P$ enough to align an internal copy of the suffix, which can be a small move; the length of the suffix is not a lower bound on the shift.

The error is dropping the clamp. When $\text{last}(c)\ge j$ this is $\le 0$; the correct rule is $\max (1,j-\text{last}(c))$ so the pattern always advances.

That is only Case 1. It forgets Case 2: when no full copy exists, you must align a prefix of $P$ that equals a suffix of the good suffix. Skipping Case 2 over-shifts and misses real matches.

No — the character preceding the internal copy must differ from $P[j]$. If it were equal, the next comparison would reproduce the very same mismatch, wasting the shift.

Wrong for overlapping matches. Jumping by $m$ can leap past an occurrence that overlaps the current one; you must shift by $G[0]$, which respects the pattern's self-overlap (its border). $\text{last}$ ::: table for bad character costs $O(|\Sigma |)$ extra space too, but that is a memory note, not this error.

The defining feature is the opposite: the inner loop starts at $j=m-1$ and decreases $j$. Left-to-right scanning removes the suffix knowledge every skip relies on.

No. Both heuristics preprocess only the pattern $P$ (and the alphabet). $T$ is untouched until the search phase — this is why BM handles searching one $P$ over many texts efficiently.

So that a mismatch leaves behind a matched suffix, which unlocks the good-suffix jump and lets the bad text char be aligned with its rightmost copy in $P$ — both large-skip mechanisms need suffix information.

Aligning with the leftmost copy could shift $P$ so far that it leaps over an alignment where the rightmost copy would have matched — that would skip a possible match. The rightmost-to-the-left copy is the largest safe jump.

Adding could over-shift and skip a match. Each shift is separately the largest guaranteed-safe move for its own reason; the true safe move is whichever safe reason permits more, i.e. the maximum.

When the bad char $c$ equals a character occurring late in $P$ (so $\text{last}(c)\ge j$), the formula clamps to $1$. This is the exact scenario where the good-suffix rule must rescue the shift.

With many distinct symbols, a random text char is unlikely to appear in $P$, so mismatches frequently hit the "not in $P$" case and jump the full pattern width — skipping many characters unread.

We cannot guarantee it. The mismatched text char may equal a pattern char sitting to the right of $j$, making $\text{last}(c)>j$ perfectly possible on ordinary inputs, so the clamp is mandatory, not defensive fluff.

When $P$ and $T$ share a single repeated symbol (e.g. all a), every alignment matches almost fully then mismatches, giving tiny shifts of $1$ and near-full re-scans each time — the skips vanish. The Galil Rule fixes this.

Almost nothing — there is no non-empty matched suffix before the sole character, so shifts come entirely from the bad-character rule; BM degenerates to a simple "jump to next occurrence" scan.

Nearly. Distinct characters make bad-character shifts consistently large and the degenerate clamp-to-$1$ case rare, so good suffix rarely dominates — but you still keep both for correctness in the few overlap cases.

The matched suffix is empty, so the good-suffix rule offers no help ($G[m]$, its default); the shift comes purely from the bad-character rule on that first char.

$\text{last}(c)=-1$ for each such char, so any mismatch on them triggers the maximal bad-character jump of $j+1$ — these "foreign" characters are precisely what makes BM sublinear.

Yes, provided the post-match shift uses $G[0]$ (the whole-pattern border), which never leaps past an overlapping start; that is exactly why we don't blindly shift by $m$.

The good-suffix array falls back to its default $G[j+1]=m$, sliding the pattern completely past the matched region — safe because nothing in $P$ can realign with it.

The search loop condition $s\le n-m$ is immediately false, so it reports no matches without a single comparison — the correct answer, since $P$ cannot fit.