daily pastebin goal
25%
SHARE
TWEET

Knuth-Morris-Pratt algorithm

keverman Apr 15th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int KMP(char *T, char *W)
  2. {
  3.     if(W[0] == '\0')
  4.         return 0;
  5.  
  6.     std::vector<unsigned int> LSP(1, 0);
  7.  
  8.     for(char *pat = &W[1]; *pat != EOS; pat++)
  9.     {
  10.         unsigned int j = LSP.back();
  11.  
  12.         while(j > 0 && *pat != W[j]) j = LSP[--j];
  13.         if(*pat == W[j])             j++;
  14.  
  15.         LSP.push_back(j);
  16.     }
  17.  
  18.     unsigned int j = 0;
  19.  
  20.     for(unsigned int i = 0; T[i] != EOS; i++)
  21.     {
  22.         while(j > 0 && T[i] != W[j])
  23.             j = LSP[--j];
  24.  
  25.         if(T[i] == W[j])
  26.             if(++j == LSP.size())
  27.                 return i + 1 - j;
  28.     }
  29.  
  30.     return -1;
  31. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top