Searching a long song for a melody: when a note doesn't match, you don't restart from scratch; you remember how much of the melody you'd already heard and continue from there.
Clues that point here
→ Find all occurrences of a pattern
→ Repeated substrings
→ Longest prefix that is also a suffix
→ Compare many substrings quickly
→ Shortest palindrome by adding characters
Not this pattern when
✕ The text is tiny (String.indexOf is fine)
✕ You need fuzzy matching (edit distance instead)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
String Matching (KMP, Z, Rolling Hash) · template
// KMP failure function: lps[i] = length of the longest proper prefix of p[0..i] that is also a suffix
int[] lps = new int[p.length()];
for (int i = 1, len = 0; i < p.length(); ) {
if (p.charAt(i) == p.charAt(len)) lps[i++] = ++len;
else if (len > 0) len = lps[len - 1];
else lps[i++] = 0;
}
// search: j = matched length in p
for (int i = 0, j = 0; i < t.length(); i++) {
while (j > 0 && t.charAt(i) != p.charAt(j)) j = lps[j - 1];
if (t.charAt(i) == p.charAt(j)) j++;
if (j == p.length()) { /* match ends at i */ j = lps[j - 1]; }
}