题目 | ABCBAC - 颢天笔记

AtCoder Beginner Contest 284

F - ABCBAC

https://atcoder.jp/contests/abc284/tasks/abc284_f

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $500$ points

Problem Statement

For a string $S$ of length $N$ and an integer $i (0 \leq i \leq N)$ , let us define the string $f_{i} (S)$ as the concatenation of:

the first $i$ characters of $S$ ,
the reversal of $S$ , and
the last $(N - i)$ characters of $S$ ,

in this order. For instance, if $S =$ abc and $i = 2$ , we have $f_{i} (S) =$ abcbac.

You are given a string $T$ of length $2 N$ . Find a pair of a string $S$ of length $N$ and an integer $i (0 \leq i \leq N)$ such that $f_{i} (S) = T$ . If no such pair of $S$ and $i$ exists, report that fact.

Constraints

$1 \leq N \leq 10^{6}$
$N$ is an integer.
$T$ is a string of length $2 N$ consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

$N$
$T$

Output

If no pair of $S$ and $i$ satisfies the condition, print -1. Otherwise, print $S$ and $i$ , separated by a newline. If multiple pairs of $S$ and $i$ satisfy the condition, you may print any of them.

Sample Input 1

3
abcbac

Sample Output 1

abc
2

As mentioned in the problem statement, if $S =$ abc and $i = 2$ , we have $f_{i} (S) =$ abcbac, which equals $T$ , so you should print abc and $2$ .

Sample Input 2

4
abababab

Sample Output 2

abab
1

$S =$ abab and $i = 3$ also satisfy the condition.

Sample Input 3

3
agccga

Sample Output 3

cga
0

$S =$ agc and $i = 3$ also satisfy the condition.

Sample Input 4

4
atcodeer

Sample Output 4

-1

If no pair of $S$ and $i$ satisfies the condition, print -1.

题解

可以用字符串哈希的额外性质解决：https://io.zouht.com/63.html

对于一个字符串 $S : a b c d e f$ ，其逆序字符串 $S^{'} : f e d c b a$ ，分别对两个字符串预处理字符串哈希得到 $h$ 和 $h r e v$ 数组。

对于任意 $i$ ，我们可以在 $O (1)$ 时间内确定这种情况是否成立，如 $i = 2$ 时：

字符串拆分为 $a b | c d e | f$ ，首先计算两端字符串的哈希值：

$h a s h (a b) = h_{2} h a s h (f) = h_{5} - h_{4} \cdot p$

然后组合出新字符串的哈希值：

$h a s h (a b f) = h a s h (a b) \cdot p + h a s h (f)$

然后计算中间字符串的哈希值，这里利用逆序的字符串：

$h a s h (e d c) = h r e v_{4} - h r e v_{1} \cdot p^{3}$

再比对 $h a s h (a b f)$ 和 $h a s h (e d c)$ 即可确定字符串是否一致。

双哈希

自然溢出法的单次哈希确定会被测试样例卡掉 5 个点，但是使用取模两个质数的哈希就能通过。下面的代码用了 $19260817$ 和 $19660813$ 两个质数。

代码

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN = 2e6 + 10;
int N;
char T[MAXN], T_rev[MAXN];

// hash-1: 19260817
const unsigned long long MOD_1 = 19260817;
unsigned long long p_1[MAXN], h_1[MAXN], h_rev_1[MAXN];
void init_1()
{
    p_1[0] = 1;
    for (int i = 1; i <= 2 * N; i++)
    {
        p_1[i] = (p_1[i - 1] * 131) % MOD_1;
        h_1[i] = ((h_1[i - 1] * 131) % MOD_1 + T[i]) % MOD_1;
        h_rev_1[i] = ((h_rev_1[i - 1] * 131) % MOD_1 + T_rev[i]) % MOD_1;
    }
}

unsigned long long get_1(int l, int r)
{
    return (h_1[r] % MOD_1 + MOD_1 - (h_1[l - 1] * p_1[r - l + 1]) % MOD_1) % MOD_1;
}

unsigned long long get_rev_1(int l, int r)
{
    return (h_rev_1[r] % MOD_1 + MOD_1 - (h_rev_1[l - 1] * p_1[r - l + 1]) % MOD_1) % MOD_1;
}

// hash-2: 19660813
const unsigned long long MOD_2 = 19660813;
unsigned long long p_2[MAXN], h_2[MAXN], h_rev_2[MAXN];
void init_2()
{
    p_2[0] = 1;
    for (int i = 1; i <= 2 * N; i++)
    {
        p_2[i] = (p_2[i - 1] * 131) % MOD_2;
        h_2[i] = ((h_2[i - 1] * 131) % MOD_2 + T[i]) % MOD_2;
        h_rev_2[i] = ((h_rev_2[i - 1] * 131) % MOD_2 + T_rev[i]) % MOD_2;
    }
}

unsigned long long get_2(int l, int r)
{
    return (h_2[r] % MOD_2 + MOD_2 - (h_2[l - 1] * p_2[r - l + 1]) % MOD_2) % MOD_2;
}

unsigned long long get_rev_2(int l, int r)
{
    return (h_rev_2[r] % MOD_2 + MOD_2 - (h_rev_2[l - 1] * p_2[r - l + 1]) % MOD_2) % MOD_2;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> T + 1;
    for (int i = 2 * N; i >= 1; i--)
        T_rev[2 * N - i + 1] = T[i];
    init_1();
    init_2();
    for (int i = 0; i <= N; i++)
    {
        int l = N - i + 1, r = 2 * N - i;
        unsigned long long a_1 = get_rev_1(l, r),
                           a_2 = get_rev_2(l, r),
                           b_1 = get_1(1, i),
                           b_2 = get_2(1, i),
                           c_1 = get_1(i + N + 1, 2 * N),
                           c_2 = get_2(i + N + 1, 2 * N);
        if (a_1 == ((b_1 * p_1[N - i]) % MOD_1 + c_1) % MOD_1 &&
            a_2 == ((b_2 * p_2[N - i]) % MOD_2 + c_2) % MOD_2)
        {
            for (int j = i + N; j >= i + 1; j--)
                cout << T[j];
            cout << endl;
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

题目 | ABCBAC