What pattern-matching algorithm is this?

I was reading the book Theory & Problems Of Data Struc (Seym开发者_开发知识库our Lipschuz).

Let me provide an image of the section I was reading.

.

This section of the book talks about a pattern-matching algorithm named "Second Patter-Matching Algorithm".

What algorithm is this? Is this Boyer-Moore or KMP or Horspool or what?

Or, is this any new algorithm produced by the author?

---

I believe that this is the KMP algorithm. KMP constructs a "failure table" that is essentially an automaton saying "if you mismatch on a particular character, how much of the pattern string can you still be matching?" It also does a preprocessing of the pattern and not the string being matched. Moreover, if you look at the Aho-Corasick algorithm, which is a generalization of KMP, it constructs a more general version of this automaton that works on multiple patterns at once. Consequently, I'm pretty sure that you're looking at KMP.