Description

题目链接

题目大意:有一个字符串 $S$,设 $T = S + S$,在 $T$ 中任意一个位置插入一个字母形成 $U$。给定 $U$,求 $S$。

Solution

若 $n$ 为偶数时显然无解。

当 $n$ 是奇数时,考虑枚举插入的字母所在的位置。

设位置为 $i$,当 $i = \frac{n + 1}{2}$ 时,有 $H(1, \frac{n + 1}{2} - 1) = H(\frac{n + 1}{2} + 1, n)$。

同理可以列出当 $i < \frac{n + 1}{2}, i > \frac{n + 1}{2}$ 的式子。

需要用到的公式:

设进制数为 $b$。

求子串哈希:$H(l, r) = H(r) - H(l - 1) \cdot b^{r - l + 1}$。

求子串 $[l, r]$ 去掉 $p$ 的哈希:$H(l, r, p) = H(l, p - 1) \cdot b^{r - p} + H(p + 1, r)$。

然后卡了半天模数,死活过不去,遂改成自然溢出过了...

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef long long LL;
typedef unsigned long long uLL;

const uLL base = 19260817;

std::map<uLL, int> t;
uLL h[2000010], f[2000010];
int n, ans;
char s[2000010];
bool flag;

uLL hash(int l, int r) { return h[r] - h[l - 1] * f[r - l + 1]; }
uLL intervalHash(int l, int r, int p) { return hash(l, p - 1) * f[r - p] + hash(p + 1, r); }

int main() {
    read(n);
    scanf("%s", s + 1);
    if (n % 2 == 0) {
        puts("NOT POSSIBLE");
        return 0;
    }
    for (int i = 1; i <= n; ++i)    h[i] = h[i - 1] * base + s[i] - 'A' + 1;
    f[0] = 1;
    for (int i = 1; i <= n; ++i)    f[i] = f[i - 1] * base;
    for (int i = 1; i <= n; ++i) {
        if (i == n / 2 + 1) {
            if (hash(1, i - 1) == hash(i + 1, n)) {
                if (flag && t.find(hash(1, i - 1)) == t.end()) {
                    puts("NOT UNIQUE");
                    return 0;
                }
                ++t[hash(1, i - 1)];
                flag = true;
                ans = i;
            }
        } else if (i < n / 2 + 1) {
            if (intervalHash(1, n / 2 + 1, i) == hash(n / 2 + 2, n)) {
                if (flag && t.find(hash(n / 2 + 2, n)) == t.end()) {
                    puts("NOT UNIQUE");
                    return 0;
                }
                ++t[hash(n / 2 + 2, n)];
                flag = true;
                ans = i;
            }
        } else {
            if (intervalHash(n / 2 + 1, n, i) == hash(1, n / 2)) {
                if (flag && t.find(hash(1, n / 2)) == t.end()) {
                    puts("NOT UNIQUE");
                    return 0;
                }
                ++t[hash(1, n / 2)];
                flag = true;
                ans = i;
            }
        }
    }
    if (!ans) {
        puts("NOT POSSIBLE");
        return 0;
    }
    if (ans == n / 2 + 1)    for (int i = 1; i <= n / 2; ++i)    printf("%c", s[i]);
    else if (ans < n / 2 + 1)    for (int i = n / 2 + 2; i <= n; ++i)    printf("%c", s[i]);
    else    for (int i = 1; i <= n / 2; ++i)    printf("%c", s[i]);
    puts("");
    return 0;
}
Last modification:September 5th, 2021 at 01:07 am