Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define mp make_pair
- #define pb push_back
- #define pii pair <int, int>
- #define piii pair<pii, int>
- #define vi vector<int>
- #define vpii vector<pii>
- #define read1(a) int a; scanf("%d", &a)
- #define read2(a, b) int a, b; scanf("%d %d", &a, &b)
- #define read3(a, b, c) int a, b, c; scanf("%d %d %d", &a, &b, &c)
- #define FOR(i, a, b) for (int i=a; i<b; i++)
- #define F0R(i, a) for (int i=0; i<a; i++)
- #define readgi(n) F0R(i, n) { scanf("%d", &arr[i]); }
- #define readgs(n) F0R(i, n) { scanf(" %c", &arr[i]); }
- #define f first
- #define s second
- #define usaco(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout);
- #define println1(a) printf("%d\n", a);
- #define println2(a, b) printf("%d %d\n", a, b);
- #define println3(a, b, c) printf("%d %d %d\n", a, b, c);
- #define pv(v) for (int i : v) { printf("%d ", i); } printf("\n");
- const int MOD = 1000000007;
- const int MAX = 100005;
- int zres[MAX];
- void z(string s) {
- int n = s.length();
- int l = -1; int r = -1;
- F0R(i, MAX) { zres[i] = 0; }
- FOR(i, 1, n+1) {
- if (i <= r) {
- zres[i] = min(r - i + 1, zres[i-l]);
- }
- while (i + zres[i] < n && s[i+zres[i]] == s[zres[i]]) {
- zres[i]++;
- }
- if (i + zres[i] - 1 > r) {
- l = i;
- r = i + zres[i] - 1;
- }
- }
- }
- int main()
- {
- string str;
- cin >> str;
- int l = str.length();
- z(str);
- zres[0] = l;
- F0R(i, l) { cout << zres[i] << " "; }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement