Advertisement
Guest User

Untitled

a guest
Oct 17th, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. string::size_type KMP(const string& S, int begin, const string& pattern)
  8. {
  9.     vector<int> pf(pattern.length());
  10.     pf[0] = 0;
  11.     for (int k = 0, i = 1; i < pattern.length(); ++i) {
  12.         while ((k > 0) && (pattern[i] != pattern[k])) k = pf[k - 1];
  13.         if (pattern[i] == pattern[k]) k++;
  14.         pf[i] = k;
  15.     }
  16.     for (int k = 0, i = begin; i < S.length(); ++i) {
  17.         while ((k > 0) && (pattern[k] != S[i])) k = pf[k - 1];
  18.         if (pattern[k] == S[i]) k++;
  19.         if (k == pattern.length()) return (i - pattern.length() + 1);
  20.     }
  21.     return (string::npos);
  22. }
  23.  
  24. int main()
  25. {
  26.     int n;
  27.     string s, m;
  28.     cin >> n >> s;
  29.     for (int i = 0; i < n; i++) {
  30.         m += s[n - i - 1];
  31.     }
  32.     s = s + s;
  33.  
  34.     string::size_type kmp_res = KMP(s, 0, m);
  35.     if (kmp_res <= n) cout << kmp_res;
  36.     else cout << - 1;
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement