Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- // #define int long long
- #define ft first
- #define sd second
- #define all(a) a.begin(), a.end()
- typedef long long ll;
- typedef long double ld;
- const int INF = 1e9 + 5;
- void solve()
- {
- string s;
- cin >> s;
- int n = (int)(s.size());
- for (int i = 0; i < n; i++)
- {
- s.push_back(s[i]);
- }
- vector<int> z(2 * n, 0);
- int l = 0, r = 0;
- for (int i = 1; i < 2 * n; i++)
- {
- if (i <= r)
- {
- z[i] = min(r - i + 1, z[i - l]);
- }
- while (z[i] + i < 2 * n && s[z[i]] == s[z[i] + i])
- {
- z[i]++;
- }
- if (i + z[i] - 1 > r)
- {
- r = i + z[i] - 1;
- l = i;
- }
- if (z[i] >= n)
- {
- cout << i;
- return;
- }
- }
- }
- void clear()
- {
- cout << "\n";
- }
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int t = 1;
- // cin >> t;
- while (t--)
- {
- solve();
- clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement