1 条题解

  • 0
    @ 2023-11-25 18:29:43
    #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
    上传者