Where it runs
1. The problem
The plain search from step 126 has one weakness. After a mismatch it slides the pattern one step to the right and compares text characters it has already seen. That is what makes it O(n·m). KMP (the Knuth-Morris-Pratt algorithm, named after the three people who found it) fixes exactly that. It goes through the text once, left to right, and never moves back. For that it needs a small table. The table is built from the pattern alone, before the search starts, and it says where to move in the pattern on a mismatch. The result is O(n + m): linear in the length of the text plus the length of the pattern.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems about a string's prefixes that are also its suffixes, and searches that must stay O(n + m) on long inputs. The LPS table answers both, and the search never moves backward in the text.
The lesson's search, stopped at the first match. It is O(n + m) on any input.
The last value of the LPS table is the length of the longest happy prefix, so build the table and slice.
With L as the last LPS value, s is one repeated piece exactly when L is above 0 and n divides by n minus L.
Build the LPS of s, a separator and reversed s. Its last value is the longest palindrome at the start of s, and the rest gets mirrored in front.