Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <set>
- #include <map>
- #include <deque>
- #include <cmath>
- #include <queue>
- #include <string>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- #define pb push_back
- #define po pop_back()
- #define matrix vector<vector<ll>>
- #define pin(p) cin >> p.first >> p.second;
- #define mx(v) max_element(v.begin(), v.end());
- #define mn(v) min_element(v.begin(), v.end());
- #define pout(p) cout << p.first << " " << p.second;
- #define er(v, l, r) erase(v.begin() + l, v.begin() + r);
- #define vin(v, n) for(int i = 0; i < n; ++i) cin >> v[i];
- #define vout(v, n) for(int i = 0; i < n; ++i) cout << v[i];
- using namespace std;
- typedef long long ll;
- typedef long long ld;
- const ll INF = 1000LL * 1000 * 1000 * 1000 * 1000 * 1000;
- const int inf = 1000 * 1000 * 1000;
- vector<ll> hashe(100000);
- vector<ll> power(100000);
- ll truehash(int l, int r)
- {
- return hashe[r + 1] - hashe[l] * power[r - l + 1];
- }
- bool turehash(int len,string &s)
- {
- return len <= s.size() / 2 ? truehash(0, len - 1) == truehash(len, len * 2 - 1) : true;
- }
- int main()
- {
- string s;
- cin >> s;
- s.insert(s.begin(), '#');
- hashe[0] = 0;
- power[0] = 1;
- for (int i = 1; i < s.size(); ++i)
- {
- power[i] = power[i - 1] * 29;
- hashe[i] = hashe[i - 1] + (s[i] - 'a' + 1)*power[i];
- }
- for (int k = 1; k < s.size(); ++k)
- {
- if (turehash(k,s))
- {
- cout << k;
- return 0;
- }
- }
- cout << s.size()-1;
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement