Naive string matching is O(n m) and dies at n, m = 1e6. KMP builds the prefix function of pattern + '#' + text (or of the pattern alone, then streams the text).
π[i] = max { k : k < i+1 and s[0..k) = s[i-k+1..i+1) }, or 0. The recurrence: try k = π[i-1], then π[π[k]-1], until the next character matches or k = 0.
CSES String Matching / Finding Borders / Finding Periods are all π. Borders of the whole string are π[n-1], then π[π[n-1]-1], …
function prefixFunction(s) {
const n = s.length;
const pi = Array(n).fill(0);
for (let i = 1; i < n; i++) {
let j = pi[i - 1];
while (j > 0 && s[i] !== s[j]) j = pi[j - 1];
if (s[i] === s[j]) j++;
pi[i] = j;
}
return pi;
}
function findAll(text, pattern) {
const pi = prefixFunction(pattern + "#" + text);
const m = pattern.length;
const hits = [];
for (let i = 0; i < text.length; i++) {
if (pi[m + 1 + i] === m) hits.push(i - m + 1);
}
return hits;
}Checks 0/2