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* searchRabinKarp(const char* haystack, size_t haystackLength,
                            const char* needle,   size_t needleLength)
{
  if (!haystack || !needle || haystackLength < needleLength)
    return NULL;
  if (needleLength == 0)
    return haystack;
  const char* haystackEnd = haystack + haystackLength - needleLength + 1;
  haystack = (const char*)memchr(haystack, *needle, haystackLength);
  if (!haystack)
    return NULL;
  unsigned int hashNeedle   = 0;
  unsigned int hashHaystack = 0;
  size_t i;
  for (i = 0; i < needleLength; i++)
  {
    if (!haystack[i])
      return NULL;
    hashNeedle   += needle  [i];
    hashHaystack += haystack[i];
  }
  while (haystack != haystackEnd)
  {
    if (hashHaystack == hashNeedle)
    {
      if (memcmp(haystack, needle, needleLength) == 0)
        return haystack;
    }
    hashHaystack += *(haystack + needleLength);
    hashHaystack -= *haystack++;
  }
  return NULL;
}
const char * searchRabinKarp ( const char * haystack , size_t haystackLength , const char * needle , size_t needleLength ) { if ( ! haystack || ! needle || haystackLength < needleLength ) return NULL ; if ( needleLength == 0 ) return haystack ; const char * haystackEnd = haystack + haystackLength - needleLength + 1 ; haystack = ( const char * ) memchr ( haystack , * needle , haystackLength ) ; if ( ! haystack ) return NULL ; unsigned int hashNeedle = 0 ; unsigned int hashHaystack = 0 ; size_t i ; for ( i = 0 ; i < needleLength ; i ++ ) { if ( ! haystack [ i ] ) return NULL ; hashNeedle += needle [ i ] ; hashHaystack += haystack [ i ] ; } while ( haystack != haystackEnd ) { if ( hashHaystack == hashNeedle ) { if ( memcmp ( haystack , needle , needleLength ) == 0 ) return haystack ; } hashHaystack += * ( haystack + needleLength ) ; hashHaystack -= * haystack ++ ; } 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 // one byte beyond last position where a match can begin // 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 // not enough haystack left ? // walk through haystack and roll the hash computation // identical hash ? // can be a false positive, therefore must check all characters again // update hash // needle not found in haystack