Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;
- string t,s;
- int n,m;
- vector<int> b;
- void kmp_pre()
- {
- b.resize(m+1);
- b[0] = -1;
- int i=0,j=-1;
- while(i<m)
- {
- while((j>=0) && (s[i]!=s[j])) j=b[j];
- i++;j++;
- b[i] = j;
- }
- }
- vector<int> kmp()
- {
- vector<int> ans;
- int i=0,j=0;
- while(i<n)
- {
- while((j>=0) && (t[i]!=s[j])) j=b[j];
- i++; j++;
- if(j==m)
- {
- ans.push_back(i-j);
- j = b[j];
- }
- }
- return ans;
- }
- int main()
- {
- t = "I DO NOT LIKE SEVENTY SEV BUT SEVENTY SEVENTY SEVEN";
- s = "SEVENTY SEVEN";
- n = t.size(), m = s.size();
- kmp_pre();
- vector<int> ans = kmp();
- cout << "Matches: ";
- for(int e:ans) cout << e << ' ';
- cout << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment