Search "abcabcabd" for "abcabd". Try every alignment of the pattern under the text, from shift 0 to shift 3, comparing character by character and stopping at the first mismatch.
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)
}