Skip to content

Instantly share code, notes, and snippets.

@NazemMahmud
Last active December 11, 2021 20:22
Show Gist options
  • Save NazemMahmud/d51024ae81d96cf3ccbc2bc9a86e802a to your computer and use it in GitHub Desktop.
Save NazemMahmud/d51024ae81d96cf3ccbc2bc9a86e802a to your computer and use it in GitHub Desktop.
Pre process pattern string for KMP algorithm
function preProcess(pattern) {
let lps = new Array(pattern.length);
let i = 0, j = 1; lps[0] = 0;
while (j < pattern.length) {
if(pattern[j] == pattern[i]) {
lps[j] = i + 1;
i++;
j++;
} else if(i != 0) {
i = lps[i-1];
} else {
lps[j] = 0;
j++;
}
}
return lps;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment