HYSBZ 3916 （2020.3.15训练B题）

题意：给定一个字符串，只有大写字母，删掉任一个字母后，能否形成两个等长相同的子串，有且只有一个则直接输出，如果存在多个输出NOT UNIQUE，不存在输出NOT POSSIBLE

长度偶数自然不可能，然后遍历原串即可，比较子串是否相同用哈希函数

ac代码如下：

#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2000005;
const ll mod = 1e9 + 6, base = 27;
char s[maxn];
ll n, hashh[maxn], Pow[maxn];
ll gethash(ll l, ll r)
{
    return (hashh[r] - (ll)hashh[l - 1] * Pow[r - l + 1] % mod + mod) % mod;	
}
ll judge(ll pos)
{
    ll w1, w2;if (pos <= n / 2) w1 = (gethash(1, pos - 1) * Pow[n / 2 - pos + 1] % mod + gethash(pos + 1, n / 2 + 1)) % mod;else w1 = gethash(1, n / 2);if (pos > n / 2 + 1)w2 = (gethash(n / 2 + 1, pos - 1) * Pow[n / 2 - (pos - n / 2 - 1)] % mod + gethash(pos + 1, n)) % mod;else w2 = gethash(n / 2 + 2, n);if (w1 == w2) return w1;else return 0;}
int main()
{
    cin >> n;scanf("%s", s + 1);Pow[0] = 1;if (n%2 == 0){
    cout << "NOT POSSIBLE"<<endl;return 0;}for (int i = 1; i <= n; i++){
    hashh[i] = (hashh[i - 1] * base + s[i] - 'A' + 1) % mod;}for (int i = 1; i <= n; i++){
    Pow[i] = Pow[i - 1] * base % mod;}ll ans = 0, h = 0, w;for (int i = 1; i <= n; i++){
    if (w = judge(i)){
    if (ans == 0){
    ans = i;h = w;}else if (w != h){
    ans = -1;}}}if (ans == 0){
    cout << "NOT POSSIBLE" << endl;return 0;}if(ans == -1){
    cout << "NOT UNIQUE" << endl;return 0;}for (ll i = 1, cnt = 0; ;i++){
    if (i != ans){
    cout << s[i];cnt++;}if (cnt == n / 2){
    break;}}cout << endl;
}