「一本通 2.1 练习 3」Friends

题目描述

给定长度为 $N$ 的字符串 $U$ 。 $U$ 是由原串 $S$ 复制两遍得到 $T=S+S$ 后，在 $T$ 的任意位置插入一个字符得到的。求原串 $S$ ：不存在输出 NOT POSSIBLE，多个本质不同输出 NOT UNIQUE，唯一则输出 $S$ 。 $2\le N\le 2000001$ 。

思路

$N$ 为偶数时不可能。 $N$ 为奇数时原串长度 $L=N/2$ 。枚举删除位置 $p$ ，利用前缀哈希 $O(1)$ 比较删除后的前半段与后半段是否相等，收集本质不同的候选 $S$ 并判唯一性。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-03-31 10:00
# update_at: 2026-03-31 10:00

import sys

BASE = 131
MOD = 1_000_000_000_000_000_003  # 64 位大质数防哈希冲突


def build_powers_and_prefixes(text: str, base: int, mod: int) -> tuple[list[int], list[int]]:
    """预处理字符串的前缀哈希值与进制幂次数组。"""
    n = len(text)
    powers = [1] * (n + 1)
    prefix_hashes = [0] * (n + 1)
    for i, ch in enumerate(text):
        powers[i + 1] = (powers[i] * base) % mod
        prefix_hashes[i + 1] = (prefix_hashes[i] * base + ord(ch)) % mod
    return powers, prefix_hashes


def segment_hash(prefix_hashes: list[int], powers: list[int], mod: int, left: int, right: int) -> int:
    """提取区间 [left, right) 的滚动哈希值。"""
    raw_hash = (prefix_hashes[right] - prefix_hashes[left] * powers[right - left]) % mod
    return raw_hash + mod if raw_hash < 0 else raw_hash


def hash_without_char(
    prefix_hashes: list[int],
    powers: list[int],
    mod: int,
    left: int,
    right: int,
    skip: int,
) -> int:
    """计算区间 [left, right) 剔除下标 skip 字符后的哈希值。"""
    left_part = segment_hash(prefix_hashes, powers, mod, left, skip)
    right_part = segment_hash(prefix_hashes, powers, mod, skip + 1, right)
    return (left_part * powers[right - skip - 1] + right_part) % mod


def find_unique_s(text: str, length: int) -> str:
    """遍历删除位置，枚举并判定是否存在唯一的原串 S。"""
    if length % 2 == 0:
        return "NOT POSSIBLE"

    half = length // 2
    powers, prefix_hashes = build_powers_and_prefixes(text, BASE, MOD)

    candidates: set[str] = set()

    for del_idx in range(length):
        if del_idx < half:
            left_hash = hash_without_char(prefix_hashes, powers, MOD, 0, half + 1, del_idx)
            right_hash = segment_hash(prefix_hashes, powers, MOD, half + 1, length)
            is_valid = left_hash == right_hash
            candidate_str = text[half + 1 :]
        elif del_idx == half:
            left_hash = segment_hash(prefix_hashes, powers, MOD, 0, half)
            right_hash = segment_hash(prefix_hashes, powers, MOD, half + 1, length)
            is_valid = left_hash == right_hash
            candidate_str = text[:half]
        else:
            left_hash = segment_hash(prefix_hashes, powers, MOD, 0, half)
            right_hash = hash_without_char(prefix_hashes, powers, MOD, half, length, del_idx)
            is_valid = left_hash == right_hash
            candidate_str = text[:half]

        if is_valid:
            candidates.add(candidate_str)
            if len(candidates) > 1:
                return "NOT UNIQUE"

    if not candidates:
        return "NOT POSSIBLE"
    return next(iter(candidates))


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n_token = next(data, None)
    if n_token is None:
        return
    n = int(n_token)
    text = next(data).decode()
    result = find_unique_s(text, n)
    print(result)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:12
 * update_at: 2026-10-06 00:12
 */
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

const int MAXN = 2000005;
const ll BASE = 131;
const ll MOD = 1000000000000000003LL; // 64 位大质数

char s[MAXN];
ll pw[MAXN];      // BASE 的幂次
ll pre[MAXN];     // 前缀哈希

// 获取子串 [l, r) 的哈希值，下标从 0 开始
ll get_hash(int l, int r) {
    ll res = pre[r] - pre[l] * pw[r - l] % MOD;
    if (res < 0) res += MOD;
    return res;
}

// 获取区间 [l, r) 删除位置 p（l <= p < r）后的哈希值
ll hash_without(int l, int r, int p) {
    ll left = get_hash(l, p);
    ll right = get_hash(p + 1, r);
    return (left * pw[r - p - 1] % MOD + right) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    cin >> (s + 1); // 让 s[1..n] 有效，但逻辑里转 0 基更方便，这里读入后统一用 0 基数组 s[0..n-1]
    // 重新处理：把 s[1..n] 移到 s[0..n-1]
    for (int i = 1; i <= n; ++i) s[i - 1] = s[i];

    if (n % 2 == 0) {
        cout << "NOT POSSIBLE\n";
        return 0;
    }

    int L = n / 2; // 原串长度

    pw[0] = 1;
    for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * BASE % MOD;

    pre[0] = 0;
    for (int i = 0; i < n; ++i) {
        pre[i + 1] = (pre[i] * BASE + (s[i] - 'A' + 1)) % MOD;
    }

    // 候选原串集合，最多只有 2 种
    string ans = "";
    bool has_ans = false;
    bool not_unique = false;

    for (int p = 0; p < n; ++p) {
        bool ok = false;
        string cand = "";
        if (p < L) {
            // 前半段 [0, L+1) 删除 p，与后半段 [L+1, n) 比较
            ll h1 = hash_without(0, L + 1, p);
            ll h2 = get_hash(L + 1, n);
            if (h1 == h2) {
                ok = true;
                cand.assign(s + L + 1, s + n); // 后半段就是原串
            }
        } else if (p == L) {
            ll h1 = get_hash(0, L);
            ll h2 = get_hash(L + 1, n);
            if (h1 == h2) {
                ok = true;
                cand.assign(s, s + L); // 前半段就是原串
            }
        } else {
            // 后半段 [L, n) 删除 p，与前半段 [0, L) 比较
            ll h1 = get_hash(0, L);
            ll h2 = hash_without(L, n, p);
            if (h1 == h2) {
                ok = true;
                cand.assign(s, s + L); // 前半段就是原串
            }
        }

        if (ok) {
            if (!has_ans) {
                has_ans = true;
                ans = cand;
            } else if (ans != cand) {
                not_unique = true;
                break;
            }
        }
    }

    if (not_unique) {
        cout << "NOT UNIQUE\n";
    } else if (!has_ans) {
        cout << "NOT POSSIBLE\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

「一本通 2.1 练习 3」Friends

目录

题目描述

思路

参考代码