Advertisement
Guest User

Untitled

a guest
Oct 17th, 2019
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 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]))
  13. k = pf[k - 1];
  14. if (pattern[i] == pattern[k])
  15. k++;
  16. pf[i] = k;
  17. }
  18. for (int k = 0, i = begin; i < S.length(); ++i) {
  19. while ((k > 0) && (pattern[k] != S[i]))
  20. k = pf[k - 1];
  21. if (pattern[k] == S[i])
  22. k++;
  23. if (k == pattern.length())
  24. return (i - pattern.length() + 1); //либо продолжаем поиск следующих вхождений
  25. }
  26. return (string::npos);
  27. }
  28.  
  29. int main()
  30. {
  31. int n;
  32. cin >> n;
  33. string s;
  34. string m;
  35. cin >> s;
  36. for (int i = 0; i < n; i++) {
  37. m += s[n - i - 1];
  38. }
  39. s = s + s;
  40. //теперь s это удвоенная строка a m перевернутая
  41. //теперь хреначим поиск переврнутой в удвоенной
  42. if (KMP(s, 0, m) <= n)
  43. cout << KMP(s, 0, m);
  44. else
  45. cout << - 1;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement