DDOSvoid's Blog

Luogu P5446 [THUPC2018]绿绿和串串

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P5446

简要题解：给定一个字符串 $S$，求 $S$ 有多少前缀 $T$，满足 $T$ 进行若干次操作后得到的串 $T’$ 存在一个前缀为 $S$，字符串 $S$ 进行一次操作定义为固定 $S$ 的最后一个字符，将剩下的字符翻转并且拼接到 $S$ 的后面，例如 $abcd$ 操作一次后得到 $abcdcba$

$|S|\le 10^6$

Solution

我们如果前缀 $i$ 合法，那么前缀 $2\times i-1$ 一定也合法，反之亦然，同时对于 $2\times k -1>n$ 的前缀 $k$，$k$ 合法的条件为以 $k$ 为中心的极大回文子串的右端点为 $n$，有这个条件后我们用 $manacher$ 求每个位置作为回文中心的极大回文子串长度然后倒推即可

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
#include <iostream>
#include <cstring>
#define maxn 1000010
#define ll long long
using namespace std;

int n;
char s[maxn];

struct Manacher {
    int n, l, f[maxn * 2], Len; 
    char s[maxn * 2]; 

    void init(char *c) {
        l = strlen(c + 1); s[0] = '~'; 
        for (int i = 1, j = 2; i <= l; ++i, j += 2)
            s[j] = c[i], s[j - 1] = '#';
        n = 2 * l + 1; s[n] = '#'; s[n + 1] = '\0';
    }
    void manacher() {
        int p = 0, mr = 0;
        for (int i = 1; i <= n; ++i) f[i] = 0;
        for (int i = 1; i <= n; ++i) {
            if (i < mr) f[i] = min(f[2 * p - i], mr - i);
            while (s[i + f[i]] == s[i - f[i]]) ++f[i]; --f[i];
            if (f[i] + i > mr) mr = i + f[i], p = i;
            Len = max(Len, f[i]); 
        }
    }

    pair<int, int> a[maxn]; bool vis[maxn];
    void solve() {
        for (int i = 1; i <= l; ++i) a[i] = make_pair(0, 0), vis[i] = 0; 
        for (int i = 1; i <= n; ++i) {
            int L = i - f[i] + 1 >> 1, R = i + f[i] - 1 >> 1, len = R - L + 1; 
            if (!f[i]) continue;
            if (len & 1) a[L + len / 2] = make_pair(L, R);
        } 
        for (int i = l; i; --i) 
            if (a[i].second == l ||
                a[i].first == 1 && 2 * i - 1 <= l && vis[2 * i - 1]) vis[i] = 1;
        for (int i = 1; i <= l; ++i)
            if (vis[i]) cout << i << " ";
        cout << "\n";
    }
} M;

void work() {
    cin >> s + 1; n = strlen(s + 1); 
    M.init(s), M.manacher(), M.solve();
}

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

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}