Skip to content

Instantly share code, notes, and snippets.

View RomanovYurii's full-sized avatar

Yurii Romanov RomanovYurii

View GitHub Profile
@razwan
razwan / kmp.js
Last active August 5, 2020 23:07
Implementation of the KMP pattern-matching alghoritm in JavaScript
// processing time O(m)
// added space O(m)
// time complexity: O(n+m)
function errorTable (p, m, f) {
for (var j = 1; j <= m-1; j++) {
k = f[j-1];
while (k!=-1 && p[j-1] != p[k]) {
k = f[k];
}