Cooler_

approximate string matching with bitwise

Oct 9th, 2012
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.75 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <limits.h>
  4.  
  5. const char *search(const char *text, const char *pattern)
  6. {
  7.  int num = strlen(pattern),i=0;
  8.  unsigned long X;
  9.  unsigned long mask[CHAR_MAX+1];
  10.  
  11.   if (pattern[0] == '\0')
  12.    return text;
  13.  
  14.   if (num > 31)
  15.    return "The pattern is too long!";
  16.  
  17.   X = ~1;
  18.  
  19.   for (i=0; i <= CHAR_MAX; ++i)
  20.    mask[i] = ~0;
  21.  
  22.   for (i=0; i < num; ++i)
  23.    mask[pattern[i]] &= ~(1UL << i);
  24.  
  25.   for (i=0; text[i] != '\0'; ++i)
  26.   {
  27.    X |= mask[text[i]];
  28.    X <<= 1;
  29.    if (!(X & (1UL << num)))
  30.     return (text + i - num) + 1;
  31.   }
  32.  
  33.  return NULL;
  34. }
  35.  
  36.  
  37. int main()
  38. {
  39.  puts(search("ola cara","macaco"));
  40.  puts(search("ola cara","cara"));
  41.  puts(search("ola cara","la"));
  42.  
  43.  return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment