Complexity of right-to-left Knuth-Morris-Pratt algorithm

Suppose we modify the Knuth-Morris-Pratt string-matching algorithm to scan the pattern right-to-left a la Boyer-Moore, and consequently apply the shift rule on the right side of the cursor instead of the left side. The quantity $$\text{sp}_i(P)$$ is now defined as the length of the longest proper prefix-suffix of $$P[i\dots n]$$ instead of $$P[1\dots i]$$. We also keep two extra indices $$a,b$$ to remember where the last shift occurred:

text |---------------------------------------------------|
<<<<<<<<<<<<<<< scan
pattern |-------------|_α_|-----|_α_|
^         |   |
fail      |   |
shift >>>>>>>>> |-------------|_α_|-----|_α_|
^   ^
a   b


So we may skip $$P[a,b]$$ during the next scan. Do we still achieve a linear time complexity? Can you provide a counter-example?

For context, I was trying to see the limitations of Knuth-Morris-Pratt when going right-to-left wrt. Boyer-Moore. I now realize that right-to-left Knuth-Morris-Pratt's shift rule ($$\alpha$$) can probably be seen as a weaker version of Boyer-Moore's good suffix rule ($$\beta$$):

                          <<<<<<<<<<<<<<< scan
pattern |-------------|_α_|-----|_α_|
|______β______|
|______β______|
^
fail


So a better question would probably be whether Boyer-Moore without the bad character rule becomes linear if we keep two extra indices $$a,b$$:

text |---------------------------------------------------|
<<<<<<<<<<<<<<< scan
pattern |-------------|______β______|
|______β__|___|         |
^             |
fail          |
shift >>>>>>>>> |---|---------|___|__β______|
|______β______|
^             ^
a             b


So we may again skip $$P[a,b]$$ during the next scan.

I understand this is getting somewhat confusing so I'll consider deleting the question altogether.

• But it's not as trivial in this case, is it? The next scan may reach left of index $a$ and keep comparing symbols of the text that have already been compared before, which is something that doesn't happen left-to-right afaics. Oct 26, 2022 at 11:38