Cacher is the code snippet organizer for pro developers

// TODO : implement multi patterns finding (where the KR algo really shines)
// otherwise a simple and native indexOf(...) should be faster right ?

const KR = function(str, pattern, cb) {
  const n = str.length;
  const m = pattern.length;
  
  // bit at pattern.length-1 set to 1
  // we are going to use it when rolling hash
  let d = Math.pow(2, m - 1);
  
  const rollingHash = (previous, next, hash) => ((hash - previous.charCodeAt(0)*d) << 1) + next.charCodeAt(0);
  
  let hstr = 0;
  let hpattern = 0;
  for (let i = 0; i < m; i++) {
    hstr = (hstr << 1) + str.charCodeAt(i);
    hpattern = (hpattern << 1) + pattern.charCodeAt(i);
  }
  
  // Searching
  for (let j = 0; ; j++) {
    if (hstr === hpattern) {
      if (str.substring(j, j+m) === pattern.substring(0, m)) {
        cb(j)
      } else {
        console.log('false positive at ', j);
      }
    }
    
    // end of the string
    if (j + m === n) {
      break;
    }
    
    hstr = rollingHash(str[j], str[j + m], hstr);
  }
  
  
};