Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;
- string::size_type KMP(const string& S, int begin, const string& pattern)
- {
- vector<int> pf(pattern.length());
- pf[0] = 0;
- for (int k = 0, i = 1; i < pattern.length(); ++i) {
- while ((k > 0) && (pattern[i] != pattern[k]))
- k = pf[k - 1];
- if (pattern[i] == pattern[k])
- k++;
- pf[i] = k;
- }
- for (int k = 0, i = begin; i < S.length(); ++i) {
- while ((k > 0) && (pattern[k] != S[i]))
- k = pf[k - 1];
- if (pattern[k] == S[i])
- k++;
- if (k == pattern.length())
- return (i - pattern.length() + 1); //либо продолжаем поиск следующих вхождений
- }
- return (string::npos);
- }
- int main()
- {
- int n;
- cin >> n;
- string s;
- string m;
- cin >> s;
- for (int i = 0; i < n; i++) {
- m += s[n - i - 1];
- }
- s = s + s;
- //теперь s это удвоенная строка a m перевернутая
- //теперь хреначим поиск переврнутой в удвоенной
- if (KMP(s, 0, m) <= n)
- cout << KMP(s, 0, m);
- else
- cout << - 1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement