1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| #include <bits/stdc++.h> #define int LL using LL = long long; const int N = 2e7 + 100; char a[N], b[N]; int la, lb, Z[N], p[N], ans; void get_Z(char x[], int len) { Z[1] = len; for (int i = 2, l = 0, r = 0; i <= len; ++i) { if (i <= r) Z[i] = std::min(Z[i - l + 1], r - i + 1); while (Z[i] + i <= len && x[Z[i] + 1] == x[Z[i] + i]) ++Z[i]; if (i + Z[i] - 1 > r) r = i + Z[i] - 1, l = i; } } void exkmp(char x[], int len, char y[]) { for (int i = 1, l = 0, r = 0; i <= len; ++i) { if (i <= r) p[i] = std::min(Z[i - l + 1], r - i + 1); while (p[i] + i <= len && y[p[i] + 1] == x[p[i] + i]) ++p[i]; if (i + p[i] - 1 > r) r = i + p[i] - 1, l = i; } } signed main() { scanf("%s %s", a + 1, b + 1); la = strlen(a + 1), lb = strlen(b + 1); get_Z(b, lb), ans = 0; for (int i = 1; i <= lb; ++i) ans ^= (Z[i] + 1) * i; printf("%lld\n", ans); exkmp(a, la, b), ans = 0; for (int i = 1; i <= la; ++i) ans ^= (p[i] + 1) * i; printf("%lld\n", ans); return 0; }
|