【题解】P5446 [THUPC2018]绿绿和串串

CG__HeavenHealer · 2021-09-04 20:35:22 · 题解

其实本题的 Hash 解法应该更好想。

题意：

题意非常诡异：求出给定字符串的长度为 x 的一个前缀是否满足它的一个前缀翻转过来的前缀能和这个串的后缀匹配，能的话输出 x。

听起来完全听不懂

比如，对于这个串：abcdcb，4 合法是因为再 abcd 这个前缀中，有一个长度为 3 的前缀 abc，反转后为 cba，前两个字符可以匹配原串的后两个字符。

考虑一个暴力还有问题的算法：处理出原串正和反的哈希之后，n^2 扫描前缀以及前缀的前缀，之后 \Theta(1) 匹配反转后的前缀和原串的后缀。

这样就有问题了：因为这个串的前缀可以无限次反转拼接，所以像这样的一个串 qwq，可以得到 qwqwq,qwqwqwq\ldots，直接判断它可能并不能得到合法方案。

所以我们把正着扫改成倒着扫：

• 如果扫的位置在字符串的后一半，它是不可能有循环节的，直接判断即可。注意这里的长度上限是 n-i+1，因为只有前缀加上前缀的前缀的长度大于等于原串的长度时才有可能匹配成功，所以长度上限应该以原串为准；

  另外要注意，由于我们预处理的是正着的和反着的哈希值，所以考虑前缀时应该倒着考虑，即把 n 看成 1，把 i 看成 n-i+1，那么需要处理的区间设为 [1,l]，由对称关系得到 \dfrac{l+1}{2}=n-i+1，解出 l=2n-2i+1，所以判断的条件就是 Hash(i,n)=reverseHash(n-i+1,2n-2i+1)。

• 而如果扫的位置在前一半，考虑他反转过去，对应点是否合法；如果合法的话，再比较一下 Hash(i,2i-1) 是否等于 reverseHash(n-i+1,n)，目的是判断是否满足回文。显然，关于 i 回文的话，在 2i-1 和 i 这两个位置的合法性应该是相同的。比如 degede 这个串，在 3 和 5 两个位置取到的合法前缀都应该是 de。如果 2i-1 这个位置合法，i 也会合法。倒推也可以避免统计不到循环反转了好几次才合法的情况。

#include <bits/stdc++.h> 
using namespace std;
#define int long long
using ull = unsigned long long;
#define ri register int
const int N = 5e6 + 10;
const ull base = 13331;
inline int read() {
    ri x = 0, f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return f * x;
}
char s[N], rs[N];
ull hsh1[N], hsh2[N], pw[N];
bool vis[N];
inline ull Hash(int l, int r) {
    return hsh1[r] - hsh1[l - 1] * pw[r - l + 1];
}
inline ull rHash(int l, int r) {
    return hsh2[r] - hsh2[l - 1] * pw[r - l + 1];
}
inline void init() {
    memset(rs, 0, sizeof(rs));
    memset(vis, false, sizeof(vis));
    memset(hsh1, 0, sizeof(hsh1));
    memset(hsh2, 0, sizeof(hsh2));
}
signed main() {
    pw[0] = 1;
    for (ri i = 1; i < N; i++) pw[i] = pw[i - 1] * base;
    for (ri T = read(); T--; init()) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        for (ri i = 1; i <= n; i++) rs[i] = s[i];
        reverse(rs + 1, rs + n + 1);
        for (ri i = 1; i <= n; i++) 
            hsh1[i] = hsh1[i - 1] * base + (ull)s[i], 
            hsh2[i] = hsh2[i - 1] * base + (ull)rs[i];
        vis[n] = true;
        for (ri i = n - 1; i; i--) {
            if (2 * i - 1 >= n) { 
                if (Hash(i, n) == rHash(n - i + 1, n * 2 - 2 * i + 1)) vis[i] = true;
            } else {
                if (vis[2 * i - 1] && Hash(i, 2 * i - 1) == rHash(n - i + 1, n)) 
                    vis[i] = true; 
            }
        }
        for (ri i = 1; i <= n; i++) 
            if (vis[i]) printf("%lld ", i);
        putchar(10);
    }
    return 0;
}
/*
3
abcdcb
qwqwq
qaqaqqq
*/