search.c
/// Rabin-Karp algorithm
/** based on simple hash proposed by Raphael Javaux **/
Rabin-Karp algorithm
based on simple hash proposed by Raphael Javaux
Rabin - Karp algorithm based on simple hash proposed by Raphael Javaux
const char* searchRabinKarpString(const char* haystack, const char* needle)
{
  if (!haystack || !needle)
    return NULL;
  if (!*needle)
    return haystack;
  haystack = strchr(haystack, *needle);
  if (!haystack)
    return NULL;
  unsigned int hashNeedle   = *needle;
  unsigned int hashHaystack = *haystack;
  const char*  scanNeedle   = needle   + 1;
  const char*  scanHaystack = haystack + 1;
  while (*scanNeedle && *scanHaystack)
  {
    hashNeedle   += *scanNeedle++;
    hashHaystack += *scanHaystack++;
  }
  if (*scanNeedle)
    return NULL;
  const size_t needleLength = scanNeedle - needle;
  for (;;)
  {
    if (hashHaystack == hashNeedle)
    {
      if (memcmp(haystack, needle, needleLength) == 0)
        return haystack;
    }
    if (!*scanHaystack)
      break;
    hashHaystack -= *haystack++;
    hashHaystack += *scanHaystack++;
  }
  return NULL;
}
const char * searchRabinKarpString ( const char * haystack , const char * needle ) { if ( ! haystack || ! needle ) return NULL ; if ( ! * needle ) return haystack ; haystack = strchr ( haystack , * needle ) ; if ( ! haystack ) return NULL ; unsigned int hashNeedle = * needle ; unsigned int hashHaystack = * haystack ; const char * scanNeedle = needle + 1 ; const char * scanHaystack = haystack + 1 ; while ( * scanNeedle && * scanHaystack ) { hashNeedle += * scanNeedle ++ ; hashHaystack += * scanHaystack ++ ; } if ( * scanNeedle ) return NULL ; const size_t needleLength = scanNeedle - needle ; for ( ; ; ) { if ( hashHaystack == hashNeedle ) { if ( memcmp ( haystack , needle , needleLength ) == 0 ) return haystack ; } if ( ! * scanHaystack ) break ; hashHaystack -= * haystack ++ ; hashHaystack += * scanHaystack ++ ; } return NULL ; }
Rabin-Karp algorithm
based on simple hash proposed by Raphael Javaux
Rabin - Karp algorithm based on simple hash proposed by Raphael Javaux
// detect invalid input // empty needle matches everything // find first match of the first letter // now first letter of haystack and needle is identical // let's compute the sum of all characters of needle // if scanNeedle doesn't point to zero, then we have too little haystack // length of needle // walk through haystack and roll the hash // identical hash ? // can be a false positive, therefore must check all characters again // no more bytes left ? // update hash // needle not found in haystack