92pts求调
查看原帖
92pts求调
1485399
Van_Helsing楼主2025/6/17 20:30
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e7 + 10;
char a[MAXN], b[MAXN];
int z[MAXN], p[MAXN];
void getz(char *s, int m){
    int l = 0, r = 0;
    for(int i = 1; i < m; ++i){
        if(i <= r && z[i - l] < r - i + 1)
            z[i] = z[i - l];
        else{
            z[i] = max(0, r - i + 1);
            while(i + z[i] < m && s[i + z[i]] == s[z[i]]) z[i]++;
        }
        if(i + z[i] - 1 > r){
            l = i;
            r = i + z[i] - 1;
        }
    }
    z[0] = m;
}
void getp(char *a, int n, char *b, int m){
    int l = 0, r = 0;
    for(int i = 0; i < n; ++i){
        if(i > r){
            p[i] = 0;
            while(i + p[i] < n && p[i] < m && a[i + p[i]] == b[p[i]]) p[i]++;
        }else{
            int k = i - l;
            p[i] = min(z[k], r - i + 1);
            while(i + p[i] < n && p[i] < m && a[i + p[i]] == b[p[i]]) p[i]++;
        }
        if(i + p[i] - 1 > r){
            l = i;
            r = i + p[i] - 1;
        }
    }
}
int main(){
    scanf("%s%s", a, b);
    int m = strlen(b), n = strlen(a);
    getz(b, m);
    getp(a, n, b, m);
    long long ansz = 0, ansp = 0;
    for(int i = 0; i < m; ++i) ansz ^= 1LL * (i + 1) * (z[i] + 1);
    for(int i = 0; i < n; ++i) ansp ^= 1LL * (i + 1) * (p[i] + 1);
    printf("%lld\n%lld", ansz, ansp);
    return 0;
}
2025/6/17 20:30
加载中...