Hash the pattern once: h("abra") = 57, using base 31 modulo 101. Then slide a window of 4 over the text, updating its hash in O(1) by dropping the leftmost character and adding the next. Characters are compared only when the two hashes agree.
The code
String Matching, in Python
def naive(text, pattern):
found = []
for shift in range(len(text) - len(pattern) + 1):
j = 0
while j < len(pattern) and text[shift + j] == pattern[j]: # compare left to right
j += 1
if j == len(pattern): # whole pattern matched
found.append(shift)
return found
def prefix_function(p):
pi = [0] * len(p)
for i in range(1, len(p)):
k = pi[i - 1] # longest border so far
while k > 0 and p[i] != p[k]: # fall back to a shorter border
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def kmp(text, pattern):
pi = prefix_function(pattern)
found = []
j = 0 # matched pattern chars
for i in range(len(text)):
while j > 0 and text[i] != pattern[j]: # slide, keep the border
j = pi[j - 1]
if text[i] == pattern[j]:
j += 1
if j == len(pattern):
found.append(i - j + 1)
j = pi[j - 1]
return found
def rabin_karp(text, pattern, base=31, mod=101):
m = len(pattern)
target = 0
for c in pattern:
target = (target * base + ord(c)) % mod
hash = 0
for c in text[:m]:
hash = (hash * base + ord(c)) % mod
found = []
for shift in range(len(text) - m + 1):
if hash == target and text[shift:shift + m] == pattern: # verify
found.append(shift)
if shift + m < len(text):
hash = roll(hash, text[shift], text[shift + m]) # O(1)
return found
def boyer_moore(text, pattern): # bad character rule only
last = {}
for i, c in enumerate(pattern): # rightmost index
last[c] = i
found = []
shift = 0
while shift <= len(text) - len(pattern):
j = len(pattern) - 1
while j >= 0 and text[shift + j] == pattern[j]: # compare right to left
j -= 1
if j < 0:
found.append(shift)
shift += 1
else:
shift += max(1, j - last.get(text[shift + j], -1)) # line the bad char up with its last copy
return found
def z_array(s): # z[i]: longest match of s[i..] with a prefix
z = [0] * len(s)
l = r = 0 # [l, r]: rightmost match box so far
for i in range(1, len(s)):
if i <= r:
z[i] = min(r - i + 1, z[i - l]) # inside the box: copy from the mirror
while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]: # then extend by comparing
z[i] += 1
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1
return z
# matching: z of pattern + "$" + text; z[i] == m marks a match at i - m - 1
def manacher(s):
t = "#" + "#".join(s) + "#" # odd length: every centre is a character
p = [0] * len(t)
c = r = 0 # [c - r, c + r]: rightmost palindrome
for i in range(1, len(t) - 1):
if i < r:
p[i] = min(r - i, p[2 * c - i]) # inside: copy the mirror, capped by r
while (i - p[i] - 1 >= 0 and i + p[i] + 1 < len(t) and
t[i + p[i] + 1] == t[i - p[i] - 1]): # then extend one pair at a time
p[i] += 1
if i + p[i] > r: # a palindrome reaching further: new box
c, r = i, i + p[i]
k = max(range(len(p)), key=lambda i: p[i]) # radius in t is length in s
return s[(k - p[k]) // 2:(k + p[k]) // 2]
String Matching, in JavaScript
function naive(text, pattern) {
const found = [];
for (let shift = 0; shift <= text.length - pattern.length; shift++) {
let j = 0;
while (j < pattern.length && text[shift + j] === pattern[j]) j++; // compare left to right
if (j === pattern.length) found.push(shift); // whole pattern matched
}
return found;
}
function prefixFunction(p) {
const pi = new Array(p.length).fill(0);
for (let i = 1; i < p.length; i++) {
let k = pi[i - 1]; // longest border so far
while (k > 0 && p[i] !== p[k]) k = pi[k - 1]; // fall back to a shorter border
if (p[i] === p[k]) k++;
pi[i] = k;
}
return pi;
}
function kmp(text, pattern) {
const pi = prefixFunction(pattern);
const found = [];
let j = 0; // matched pattern chars
for (let i = 0; i < text.length; i++) {
while (j > 0 && text[i] !== pattern[j]) j = pi[j - 1]; // slide, keep the border
if (text[i] === pattern[j]) j++;
if (j === pattern.length) { found.push(i - j + 1); j = pi[j - 1]; }
}
return found;
}
function rabinKarp(text, pattern, base = 31, mod = 101) {
const m = pattern.length;
const target = [...pattern].reduce((h, c) => (h * base + c.charCodeAt(0)) % mod, 0);
let hash = [...text.slice(0, m)].reduce((h, c) => (h * base + c.charCodeAt(0)) % mod, 0);
const found = [];
for (let shift = 0; shift <= text.length - m; shift++) {
if (hash === target && text.slice(shift, shift + m) === pattern) found.push(shift); // verify
if (shift + m < text.length) hash = roll(hash, text[shift], text[shift + m]); // O(1)
}
return found;
}
function boyerMoore(text, pattern) { // bad character rule only
const last = new Map(); [...pattern].forEach((c, i) => last.set(c, i)); // rightmost index
const found = [];
let shift = 0;
while (shift <= text.length - pattern.length) {
let j = pattern.length - 1;
while (j >= 0 && text[shift + j] === pattern[j]) j--; // compare right to left
if (j < 0) { found.push(shift); shift += 1; }
else shift += Math.max(1, j - (last.get(text[shift + j]) ?? -1)); // line the bad char up with its last copy
}
return found;
}
function zArray(s) { // z[i]: longest match of s[i..] with a prefix
const z = new Array(s.length).fill(0); let l = 0, r = 0; // [l, r]: rightmost match box so far
for (let i = 1; i < s.length; i++) {
if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]); // inside the box: copy from the mirror
while (i + z[i] < s.length && s[z[i]] === s[i + z[i]]) z[i]++; // then extend by comparing
if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
}
return z;
} // matching: z of pattern + "$" + text; z[i] === m marks a match at i - m - 1
function manacher(s) {
const t = "#" + [...s].join("#") + "#"; // odd length: every centre is a character
const p = new Array(t.length).fill(0); let c = 0, r = 0; // [c - r, c + r]: rightmost palindrome
for (let i = 1; i < t.length - 1; i++) {
if (i < r) p[i] = Math.min(r - i, p[2 * c - i]); // inside: copy the mirror, capped by r
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < t.length &&
t[i + p[i] + 1] === t[i - p[i] - 1]) p[i]++; // then extend one pair at a time
if (i + p[i] > r) { c = i; r = i + p[i]; } // a palindrome reaching further: new box
}
const k = p.reduce((best, v, i) => (v > p[best] ? i : best), 0); // radius in t is length in s
return s.slice(Math.floor((k - p[k]) / 2), Math.floor((k + p[k]) / 2));
}
String Matching, in Kotlin
fun naive(text: String, pattern: String): List<Int> {
val found = mutableListOf<Int>()
for (shift in 0..text.length - pattern.length) {
var j = 0
while (j < pattern.length && text[shift + j] == pattern[j]) j++ // compare left to right
if (j == pattern.length) found += shift // whole pattern matched
}
return found
}
fun prefixFunction(p: String): IntArray {
val pi = IntArray(p.length)
for (i in 1 until p.length) {
var k = pi[i - 1] // longest border so far
while (k > 0 && p[i] != p[k]) k = pi[k - 1] // fall back to a shorter border
if (p[i] == p[k]) k++
pi[i] = k
}
return pi
}
fun kmp(text: String, pattern: String): List<Int> {
val pi = prefixFunction(pattern)
val found = mutableListOf<Int>()
var j = 0 // matched pattern chars
for (i in text.indices) {
while (j > 0 && text[i] != pattern[j]) j = pi[j - 1] // slide, keep the border
if (text[i] == pattern[j]) j++
if (j == pattern.length) { found += i - j + 1; j = pi[j - 1] }
}
return found
}
fun rabinKarp(text: String, pattern: String, base: Int = 31, mod: Int = 101): List<Int> {
val m = pattern.length
val target = pattern.fold(0) { h, c -> (h * base + c.code) % mod }
var hash = text.take(m).fold(0) { h, c -> (h * base + c.code) % mod }
val found = mutableListOf<Int>()
for (shift in 0..text.length - m) {
if (hash == target && text.substring(shift, shift + m) == pattern) found += shift // verify
if (shift + m < text.length) hash = roll(hash, text[shift], text[shift + m]) // O(1)
}
return found
}
fun boyerMoore(text: String, pattern: String): List<Int> { // bad character rule only
val last = HashMap<Char, Int>(); pattern.forEachIndexed { i, c -> last[c] = i } // rightmost index
val found = mutableListOf<Int>()
var shift = 0
while (shift <= text.length - pattern.length) {
var j = pattern.length - 1
while (j >= 0 && text[shift + j] == pattern[j]) j-- // compare right to left
if (j < 0) { found += shift; shift += 1 }
else shift += max(1, j - (last[text[shift + j]] ?: -1)) // line the bad char up with its last copy
}
return found
}
fun zArray(s: String): IntArray { // z[i]: longest match of s[i..] with a prefix
val z = IntArray(s.length); var l = 0; var r = 0 // [l, r]: rightmost match box so far
for (i in 1 until s.length) {
if (i <= r) z[i] = min(r - i + 1, z[i - l]) // inside the box: copy from the mirror
while (i + z[i] < s.length && s[z[i]] == s[i + z[i]]) z[i]++ // then extend by comparing
if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1 }
}
return z
} // matching: z of pattern + "$" + text; z[i] == m marks a match at i - m - 1
fun manacher(s: String): String {
val t = "#" + s.toCharArray().joinToString("#") + "#" // odd length: every centre is a character
val p = IntArray(t.length); var c = 0; var r = 0 // [c - r, c + r]: rightmost palindrome
for (i in 1 until t.length - 1) {
if (i < r) p[i] = min(r - i, p[2 * c - i]) // inside: copy the mirror, capped by r
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < t.length &&
t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++ // then extend one pair at a time
if (i + p[i] > r) { c = i; r = i + p[i] } // a palindrome reaching further: new box
}
val k = p.indices.maxBy { p[it] } // radius in t is length in s
return s.substring((k - p[k]) / 2, (k + p[k]) / 2)
}