matbensch

KMP C++

Jan 22nd, 2023 (edited)
172
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. string t,s;
  8. int n,m;
  9. vector<int> b;
  10.  
  11. void kmp_pre()
  12. {
  13.     b.resize(m+1);
  14.     b[0] = -1;
  15.  
  16.     int i=0,j=-1;
  17.     while(i<m)
  18.     {
  19.         while((j>=0) && (s[i]!=s[j])) j=b[j];
  20.         i++;j++;
  21.         b[i] = j;
  22.     }
  23. }
  24.  
  25. vector<int> kmp()
  26. {
  27.     vector<int> ans;
  28.     int i=0,j=0;
  29.     while(i<n)
  30.     {
  31.         while((j>=0) && (t[i]!=s[j])) j=b[j];
  32.         i++; j++;
  33.         if(j==m)
  34.         {
  35.             ans.push_back(i-j);
  36.             j = b[j];
  37.         }
  38.     }
  39.     return ans;
  40. }
  41.  
  42. int main()
  43. {
  44.     t = "I DO NOT LIKE SEVENTY SEV BUT SEVENTY SEVENTY SEVEN";
  45.     s = "SEVENTY SEVEN";
  46.     n = t.size(), m = s.size();
  47.     kmp_pre();
  48.     vector<int> ans = kmp();
  49.  
  50.     cout << "Matches: ";
  51.     for(int e:ans) cout << e << ' ';
  52.     cout << '\n';
  53. }
Advertisement
Add Comment
Please, Sign In to add comment