Skip to content

Instantly share code, notes, and snippets.

@Kamilczak020
Created October 16, 2017 21:58
Show Gist options
  • Save Kamilczak020/f8382eef9777e8f07d47be29a4efc04b to your computer and use it in GitHub Desktop.
Save Kamilczak020/f8382eef9777e8f07d47be29a4efc04b to your computer and use it in GitHub Desktop.
Boyer Moore string search algorithm implementation in Javascript
/**
* Returns the index of the first occurence of given string in the phrase
* In case of no match, returns -1
*
* @param text string to be searched
* @param pattern string to be found in the text
*/
export function boyerMooreSearch(text: string, pattern: string): number {
// Handle edge case
if (pattern.length === 0) {
return -1;
}
let charTable = makeCharTable(pattern);
let offsetTable = makeOffsetTable(pattern);
for (let i = pattern.length - 1, j; i < text.length;) {
for (j = pattern.length - 1; pattern[j] == text[i]; i--, j--) {
if (j === 0) {
return i;
}
}
const charCode = text.charCodeAt(i);
i+= Math.max(offsetTable[pattern.length - 1 - j], charTable[charCode]);
}
return -1;
}
/**
* Creates jump table, based on mismatched character information
*/
function makeCharTable(pattern: string): number[] {
let table = [];
// 65536 being the max value of char + 1
for (let i = 0; i < 65536; i++) {
table.push(pattern.length);
}
for (let i = 0; i < pattern.length - 1; i++) {
const charCode = pattern.charCodeAt(i);
table[charCode] = pattern.length - 1 - i;
}
return table;
}
function makeOffsetTable(pattern: string): number[] {
let table = [];
table.length = pattern.length;
let lastPrefixPosition = pattern.length;
for (let i = pattern.length; i > 0; i--) {
if (isPrefix(pattern, i)) {
lastPrefixPosition = i;
}
table[pattern.length - i] = lastPrefixPosition - 1 + pattern.length;
}
for (let i = 0; i < pattern.length - 1; i++) {
const slen = suffixLength(pattern, i);
table[slen] = pattern.length - 1 - i + slen;
}
return table;
}
function isPrefix(pattern: string, p: number): boolean {
for (let i = p, j = 0; i < pattern.length; i++, j++) {
if (pattern[i] != pattern[j]) {
return false;
}
return true;
}
}
function suffixLength(pattern: string, p: number) {
let len = 0;
for (let i = p, j = pattern.length - 1; i >= 0 && pattern[i] == pattern[j]; i--, j--) {
len += 1;
}
return len;
}
@subzero10
Copy link

I think there's a typo here, shouldn't the return statement in Line 80 be outside the for loop?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment