1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int MAXLEN = 20000000; // a, b长度的最大值 string a, b; int aLen, bLen; // 把s的z函数数组求出来 int z[MAXLEN + 5]; void getZ(const string &s) { int l, r; // s[l]~s[r] 与 s 开头 r-l+1 个字符相同 l = -1, r = -1; z[0] = 0; for (int i = 1; i < s.length(); i++) { z[i] = 0; if (l <= i && i <= r) // s[0]~s[r-l] == s[l]~s[r] // s[i-l] == s[i] // s[i-l]~s[r-l] == s[i]~s[r] // z[i-l]: s[i-l] 开始的 z[i-l] 这么多个字符和开头的这么多个字符相同 z[i] = min(z[i - l], r - i + 1); // i开始已有 z[i] 长度与开头相等 // 如果 i 开始的第 z[i]+1 个位置 // 与开头开始的第 z[i]+1 个位置相等z[i]就可以多一个长度 while (i + z[i] < s.length() && z[i] < s.length() && s[i + z[i]] == s[0 + z[i]]) z[i]++; // s[i] 开始的 z[i] 个字符,与开头的 z[i] 个字符相等 // s[i]~s[i+z[i]-1] if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } z[0] = s.length(); } // b 与 a 的每一个后缀的 LCP 长度数组 zz。 int zz[MAXLEN + 5]; void getZZ(const string &a, const string &b) { // z[i] : b[0]~ 与 b[i]~ 的 lcp getZ(b); // zz[i] : b[0]~ 与 a[i]~ 的 lcp int l, r; // b[0] ~ b[r-l] == a[l] ~ a[r] l = -1, r = -1; for (int i = 0; i < a.length(); i++) { zz[i] = 0; if (l <= i && i <= r) // b[0]~s[r-l] == a[l]~a[r] // b[i-l] == a[i] // 1: b[i-l]~s[r-l] == a[i]~a[r] // 2: b[i-l] 开始的 z[i-l] 个字符与 b 开头的 z[i - l] 个字符相等 // 由 1,2 可得 zz[i] 可以以 z[i-l] 作为基础 zz[i] = min(z[i - l], r - i + 1); // a[i] 开始已有 zz[i] 长度与 b 开头相等 // 如果 a[i] 开始的第 zz[i]+1 个位置 // 与 b[0] 开始的第 zz[i]+1 个位置相等 // 那么 z[i]就可以多一个长度 while (i + zz[i] < a.length() && zz[i] < b.length() && a[i + zz[i]] == b[0 + zz[i]]) zz[i]++; // s[i] 开始的 z[i] 个字符,与开头的 z[i] 个字符相等 // s[i]~s[i+z[i]-1] if (i + zz[i] - 1 > r) l = i, r = i + zz[i] - 1; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> a >> b; aLen = a.length(); bLen = b.length(); getZZ(a, b); long long ans; ans = 0; for (long long i = 0; i <= bLen - 1; i++) ans = ans ^ ((i + 1) * (z[i] + 1)); cout << ans << "\n"; ans = 0; for (long long i = 0; i <= aLen - 1; i++) ans = ans ^ ((i + 1) * (zz[i] + 1)); cout << ans << "\n"; return 0; }
信息
- ID
- 1371
- 时间
- 1000ms
- 内存
- 500MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 2
- 上传者