信息
- ID
- 1371
- 时间
- 1000ms
- 内存
- 500MiB
- 难度
- 5
- 标签
- 递交数
- 4
- 已通过
- 2
- 上传者
#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;
}