Skip to content

Instantly share code, notes, and snippets.

@NazemMahmud
Last active December 11, 2021 20:30
Show Gist options
  • Save NazemMahmud/66d8070cf80420fb682c41fe9e452a34 to your computer and use it in GitHub Desktop.
Save NazemMahmud/66d8070cf80420fb682c41fe9e452a34 to your computer and use it in GitHub Desktop.
KMP algorithm for substring search
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
function KMP(text, pattern){
let LPS = preProcess(pattern);
let i=0, j=0;
while(i < text.length && j < pattern.length){
if(text[i] == pattern[j]){
i++;
j++;
} else if(j!=0){
j = LPS[j-1];
} else {
i++;
}
}
if(j == pattern.length){
return true; // if you want to return the position, then (i - j )
}
return false;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment