22pts求指正
查看原帖
22pts求指正
681982
isxi楼主2023/11/6 11:14
#include "bits/stdc++.h"
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef map<int,int> MII;
typedef map<long ,long > MLL;

#define all(u) u.begin(), u.end()
#define endl '\n'
#define ff first
#define ss second
#define eb emplace_back
#define all(u) u.begin(), u.end()
#define debug(x) cout<<#x<<":"<<x<<endl;

const int inf = 0x3f3f3f3f;
//const LL inf = 1e18;// long long 才用
const int N = 2e7 + 5, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;

int z[N<<1];
int p[N<<1];
void get_z(string s,int n){//扩展kmp函数求本串和不同后缀串的最长公共前缀的长度   第一问
    z[1] = n;
    for(int i=2,l=0,r=0;i<=n;i++){
        if(i<=r) z[i] = min(z[i-l+1],r-i+1);
        while(s[1+z[i]] == s[i+z[i]]) z[i]++;
        if(i+z[i]-1>r) l = i,r = i+z[i]-1;
    }
}


void get_p(string s,int n,string t,int m){
    for(int i=1,l,r=0;i<=m;i++){
        if(i<=r) p[i] = min(z[i-l+1],r-i+1);
        while(1+p[i]<=n&&i+p[i]<=m&&s[1+p[i]]==t[i+p[i]]) p[i]++;
        if(i+p[i]-1>r) l = i,r = i+p[i]-1;
    }
}

void solve(){
    string s,t;
    cin>>s>>t;
    int n1=s.length();
    int n2 = t.length();
    s = "?"+s;
    t = "?"+t;
    get_z(t,n2);
    get_p(t,n2,s,n1);
    LL ans1=0,ans2=0;
    for(int i=1;i<=n2;i++){
        ans1 ^= (LL)(i*(z[i]+1));
    }
    for(int i=1;i<=n1;i++){
        ans2 ^= (LL)(i*(p[i]+1));
    }   
    cout<<ans1<<endl<<ans2<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t=1;
    if(cases)
        cin>>t;
    while(t--){
        solve();
    }
    return 0;
} 


看了一遍教程后自己模仿着写了一遍,能通过样例但是不知道为啥wa了,检查了一下感觉没什么问题,有没有高手能指点一下蒟蒻,感谢

2023/11/6 11:14
加载中...