Algorithm

Why do we use KMP Algorithm (LPS Array)?

When we search for a pattern in a text using a basic approach, we often end up checking the same characters again after a mismatch. This makes the process slow, especially if the pattern has repeated parts.

The KMP algorithm avoids this by using a helper array called the LPS (Longest Prefix which is also Suffix) array. It tells us how much of the pattern we can skip when a mismatch happens.

This helps us search the pattern in the text quickly without going backward in the text or rechecking already matched characters.

First, create the LPS array. It stores, for each index, the length of the longest prefix of the pattern which is also a suffix.
Start matching the pattern with the text from left to right.
If the characters match, move forward in both the pattern and the text.
If there’s a mismatch after some matches, use the LPS array to move the pattern pointer to the correct position without going back in the text.
When the whole pattern matches, store the index and continue searching using LPS.
Repeat this process until the entire text has been checked.
Return all the starting positions where the pattern is found in the text.