KMP Algorithm or LPS array

Hard

LPS tells you how far to fall back

Problem

Build the LPS (longest proper prefix-suffix) array and use it for KMP pattern matching in O(n+m).

In simple words

For each position, store the longest border (prefix that is also a suffix) — the heart of KMP.

The idea

The LPS array stores, for each prefix, the length of the longest proper prefix that is also a suffix. On a mismatch, that value says how far back the pattern can slide without missing a match, so the text pointer never moves backwards and the search is O(n + m).

The trick

The text index only ever moves forward — that is the whole gain.
On a mismatch, jump the pattern index to lps[j-1] rather than restarting at 0.
Building the LPS is the same self-matching loop applied to the pattern.

←→stepspaceplay

1/9

Brute force

timeO(n·m)spaceO(1)

Slide and compare.

1for (let i = 0; i + m <= n; i++) {2  let j = 0;3  while (j < m && text[i + j] === pat[j]) j++;4  if (j === m) return i;5}

Input

array: [a, b, x, a, b, c, a, b, c, a, b, y]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: s = "ababd"
Output:: [0, 0, 1, 2, 0]
Explanation:: Longest prefix-that-is-also-suffix at each spot.

Example 2

Input:: s = "aaaa"
Output:: [0, 1, 2, 3]
Explanation:: Each extends the previous → 0,1,2,3.

Example 3

Input:: s = "abc"
Output:: [0, 0, 0]
Explanation:: No repeats → all 0.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.