哈希超时求调
查看原帖
哈希超时求调
974277
水星湖psgqwq楼主2024/3/24 18:14
#include <bits/stdc++.h>
#define int long long
const int P = 131;
using namespace std;
int n;
unsigned int p[2000005] ,h[2000005];
string s;

unsigned int gett(int l,int r){
    return h[r] - h[l-1] * p[r - l + 1];
}

unsigned int get(int l,int r,int k){
    return gett(l,k-1)*p[r-k]+gett(k+1,r);
}

signed main()
{
    cin>>n>>s;
    s = " " + s;
    p[0] = 1;
    for(int i=1;i<=n;i++){
        p[i] = p[i-1] * P;
        h[i] = h[i-1] * P + s[i];
    }
    unordered_set<string> ans;
    string t = s.substr(n/2+2);
    for(int i=1;i<=n/2+1;i++){
        if(get(1,n/2+1,i) == gett(n/2+2,n))
            ans.insert(t);
        if(ans.size() > 1){
            cout << "NOT UNIQUE" << endl;
            return 0;
        }
    }
    t = s.substr(1,n/2);
    for(int i=n/2+1;i<=n;i++){
        if(get(n/2+1,n,i) == gett(1,n/2))
            ans.insert(t);
        if(ans.size() > 1){
            cout << "NOT UNIQUE" << endl;
            return 0;
        }
    }
    if(ans.size() == 1) cout << *ans.begin() << endl;
    else cout << "NOT POSSIBLE" << endl;
    return 0;
}
2024/3/24 18:14
加载中...