51nod- 2619 三個好朋友（裸哈希）

​​51 nod-2619 三個好朋友​​

題目

首先有一個字元串 S，兩個S拼接變成字元串 T，接着在 T 中插入一個字元變成了字元串 U。題目給出 U串，求是否存在原 S串。

輸出一行,若S不存在,輸出"NOT POSSIBLE".若S不唯一,輸出"NOT UNIQUE".否則輸出S。

分析

想暴力思路，對于每一位都假設是添加進去的，模拟删除之後兩個字元串的左右是否相同。複雜度 O（n^2），肯定不行。

複雜度主要在比較字元串上，現在對整個字元串進行​​HASH​​，比較左右兩部分時隻比較HASH值，比較一次 O（1）。總的O（n）。

例：AGEDEF 哈希值（_hash數組存的東西）：

x 是自己指定的值。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 9999991;
const ull base = 23333;
const int N = 2e6 + 10;

ull _hash[N], p[N], pre;         // 用 ull 自然溢出
int n, cnt;
char str[N], ans[N];

inline ull get(int l, int r){
    return _hash[r] - _hash[l - 1] * p[r - l + 1];
}

inline int cal(int pos){
    ull l, r;
    int mid = (n >> 1) + 1;
    if(pos < mid){
        l = get(1, pos - 1) * p[mid - pos] + get(pos + 1, mid);
        r = get(mid + 1, n);
    }else if(pos == mid){
        l = get(1, mid - 1);
        r = get(mid + 1, n);
    }else{
        l = get(1, mid - 1);
        r = get(mid, pos - 1) * p[n - pos] + get(pos + 1, n);
    }
    if(l == r){
        if(pre == l)            //跟之前答案一樣
            return 0;
        pre = l;
        if(pos <= mid){
            for(int i = mid + 1; i <= n; i++){
                ans[i - mid] = str[i];
            }
        }else{
            for(int i = 1; i < mid; i++){
                ans[i] = str[i];
            }
        }
        return 1;
    }
    return 0;
}

int main()
{
    scanf("%d%s", &n, str + 1);
    if(!(n&1)){
        puts("NOT POSSIBLE");
        return 0;
    }
    p[0] = 1;
    for (int i = 1; i <= n; i++){            //預處理 HASH值
        p[i] = p[i - 1] * base; 
        _hash[i] = _hash[i - 1] * base + str[i];
    }
    for(int i = 1; i <= n; i++){
        cnt += cal(i);
        if(cnt > 1)
            break;
    }
    if(!cnt){
        puts("NOT POSSIBLE");
    }else{
        puts(cnt == 1 ? ans + 1 : "NOT UNIQUE");
    }
    return 0;
}