题解 P6739 【[BalticOI 2014 Day1] Three Friends】

· · 题解

题解：

注意到 U 只比 S+S=T 多一位，我们可以枚举多的是哪一位，然后按序比较剩下的字符串的前半段和后半段是否相同，时间复杂度 \Theta(n^2), 可以通过 \texttt{subtask1}。

但是，由于 Hash 的存在，我们判断两个字符串相同无需按序比较，可以 Hash \Theta(1) 判断，这样此题便做到了 \Theta(n)，可以通过 \texttt{subtask2}。

什么是 Hash

据某位学长说，所有的单 Hash 都可以卡掉，所以建议大家使用双 Hash（但是我懒）

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e6+233;
const int base=233;
const int mod=998244353; //只用了单Hash
int n,cnt,flag,mark;
int h[maxn],pw[maxn],b[30];
char a[maxn]; 
int sum(int l,int r){ //计算区间[l,r]的Hash值
    if(l>r)return 0;
    return ((h[r]-(h[l-1]*pw[r-l+1])%mod)%mod+mod)%mod;
}
int query(int pos){ //Hash判断剩下的两段是否相同，pos即断点
    int pre=0,nxt=0;
    if(pos==(n+1)/2){
        pre=h[pos-1];
        nxt=sum(pos+1,n);
        return pre==nxt;
    }
    if(pos<(n+1)/2){
        pre=((h[pos-1]*pw[(n+1)/2-pos])%mod+sum(pos+1,(n+1)/2))%mod;
        nxt=sum((n+1)/2+1,n);
        return pre==nxt;
    } 
    if(pos>(n+1)/2){
        pre=h[(n+1)/2-1];
        nxt=((sum((n+1)/2,pos-1)*pw[n-pos])%mod+sum(pos+1,n))%mod;
        return pre==nxt;
    }
}
signed main(){
    memset(b,-1,sizeof(b));
    cin>>n;
    cin>>a+1;
    int len=strlen(a+1);
    for(int i=1;i<=len;++i) //Hash预处理
        h[i]=((h[i-1]*base)%mod+(int)a[i]-'A'+1)%mod;
    pw[0]=1;
    for(int i=1;i<=n;i++)
        pw[i]=(pw[i-1]*base)%mod;
    for(int i=1;i<=n;i++) 
        if(query(i)){
            mark=i,cnt++; //记录可能的端点数量及端点位置
            if(b[a[i]-'A'+1]!=-1&&b[a[i]-'A'+1]!=i-1)flag=1;
            b[a[i]-'A'+1]=i;
        }
    if(flag&&cnt>1){cout<<"NOT UNIQUE";return 0;}
    if(cnt<1){cout<<"NOT POSSIBLE";return 0;}
    if(mark==(n+1)/2){ //输出
        for(int j=1;j<=mark-1;j++)putchar(a[j]);
    }
    else if(mark<(n+1)/2){
        for(int j=1;j<=mark-1;j++)putchar(a[j]);
        for(int j=mark+1;j<=(n+1)/2;j++)putchar(a[j]);
    }
    else if(mark>(n+1)/2){
        for(int j=(n+1)/2;j<=mark-1;j++)putchar(a[j]);
        for(int j=mark+1;j<=n;j++)putchar(a[j]);
            return 0;
        }
    return 0;
}