2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

Of course, thanks to symmetry, we still achieve a linear time complexity using the modified Knuth-Morris-Pratt algorithm.

In general, we can apply symmetries to lots of situations.

  • For example, you could switch the source and the sink of a flow network with the direction of all edges reversed.
  • For example, you can switch the source and destination in Dijkstra's algorithm, which might boost performance if the branching factor is smaller around the original destination.
  • For example, instead of selecting the next interval with earliest ending time at each iteration on the problem of scheduling the most number of nonoverlapping intervals, you can also selecting the next interval with latest starting time at each iteration.
  • Many more ...
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – giofrida
    Oct 26, 2022 at 11:38
  • $\begingroup$ @giofrida l might have misunderstood how you modified the algorithm. Can you explain your it in more detail? $\endgroup$
    – John L.
    Oct 26, 2022 at 13:27
  • $\begingroup$ I don't know if I can explain it better than I did without giving a full pseudo-code, but I edited the question to give some context. I might end up deleting it, though. $\endgroup$
    – giofrida
    Oct 26, 2022 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.