Friends

Friends

题目描述

给定一个字符串S，先将字符串S复制一次（变成双倍快乐），得到字符串T，然后在T中插入一个字符，得到字符串U。
给出字符串U，重新构造出字符串S。
所有字符串只包含大写英文字母。

输入描述

第一行一个整数N，表示字符串U的长度。 N<=2e6+1
第二行一个长度为N的字符串，表示字符串U。

输出描述

一行一个字符串，表示字符串S。
特别地：
如果字符串无法按照上述方法构造出来，输出NOT POSSIBLE；
如果字符串S不唯一，输出NOT UNIQUE。

样例

input1

7
ABXCABC

output1

ABC

input2

6
ABCDEF

output2

NOT POSSIBLE

input3

9
ABABABABA

output3

NOT UNIQUE

思路

由题可知若字符串U满足条件，则从字符串U中抽取一个字符后，得到的为两个字符串S。我们只需要枚举这个字符，然后判断能否得到两个相同的字符串即可。可采用hash来求解。
当N为偶数时，显然不满足。接下来我们枚举抽取字符的位置i，当i恰好位于中间时，左右都为字符串S；当i位于左边时，显然字符串右半部分等于S；当i位于右边时，字符串左半部分等于S。后两种情况i会把一个S分成两部分，我这里也就把它拆解成两部分比较hash值。
然后是处理S不唯一的情况。由以上分析易知S要么等于字符串左半部分l，要么等于右半部分r。在遍历过程中如能得到l和r都有满足条件的情况，只需比较l和r就行。如果不相同，说明S不唯一。

代码

#include <iostream>
#include <string>
using namespace std;
#define MAXN 2000005

typedef unsigned long long ull;
ull Hash[MAXN], power[MAXN];
const int b = 27;

int main(void) {
    int n; cin>>n;
    string s; cin>>s; s = " "+s;
    power[0] = 1;
    for (int i = 1; i <= n; ++i) power[i] = power[i - 1] * b;
    for (int i = 1; i <= n; ++i) Hash[i] = Hash[i - 1] * b + (ull)(s[i] - 'A' + 1);
    if (n % 2 == 0) {
        puts("NOT POSSIBLE");
        return 0;
    } else {
        bool l = false, r = false;
        for (int i = 1; i <= n; ++i) {
            if (i == n / 2 + 1) {
                if (Hash[n / 2] == Hash[n] - Hash[n / 2 + 1] * power[n / 2]) l = true;
            } else if (i <= n / 2) {
                if (Hash[i - 1] == Hash[n / 2 + 1 + i - 1] - Hash[n / 2 + 1] * power[i - 1] && Hash[n / 2 + 1] - Hash[i] * power[n / 2 - i + 1] == Hash[n] - Hash[n / 2 + 1 + i - 1] * power[n / 2 - i + 1]) r = true;
            } else if (i > n / 2 + 1) {
                if (Hash[i - 1] - Hash[n / 2] * power[i - n / 2 - 1] == Hash[i - n / 2 - 1] && Hash[n] - Hash[i] * power[n - i] == Hash[n / 2] - Hash[n / 2 - n + i] * power[n - i]) l = true;
            }
        }
        if(l && r){
            if(s.substr(1,n/2) == s.substr(n/2+2,n/2)) cout<<s.substr(1,n/2);
            else puts("NOT UNIQUE");
        }
        else if(l) cout<<s.substr(1,n/2);
        else if(r) cout<<s.substr(n/2+2,n/2);
        else puts("NOT POSSIBLE");
    }
    return 0;
}

第一篇博客，意思一下，哈哈^_^