P5446 [THUPC2018]绿绿和串串 题解

· · 题解

Update

由于回复篇幅过长，具体问题和回复内容放在文章末尾。

思路

1

题目给出的字符串可以是由一个子串 a 翻转而得；

而 a 也可以是由一个子串 b 翻转而得；

而 b 可以是由一个子串 c 翻转而得；

……

最终得到一个无法再翻转下去的子串 x。

而字符串本身、子串 a、子串 b、子串 c……子串 x 各自的长度就是我们要的答案。

例如：给出字符串 qwqwq ，

它可以是由子串 qwqw 翻转而得的；

而 qwqw 是由子串 qwq 翻转而得的；

而 qwq 是由子串 qw 翻转而得的；

然而， qw 无法由它的子串翻转而得。

即最终答案输出： 2 3 4 5 。

2

那么如何求每个字符串的最长翻转子串（此处不考虑字符串本身）呢？

拿例子来说：

已得 qwqwq 的最长翻转子串是 qwqw 。

qwqw 的翻转中心是最后一个的 w ，回看原串，可以发现一个由同一个 w 为翻转中心的回文串 qwq 。

再多举几个例子，就可以发现，一个字符串的最长翻转子串就是它自己去掉最短末尾回文串的一半。

还是举例子说明：

qwqw 的最短末尾回文串为 wqw ，

根据上文所说，我们去掉该回文串的后半部分 w ，

然后再拿剩下的和前面组合，就可以得到 qwqw 的最长翻转子串为：

q + wq = qwq 。

现在，我们的问题就转化为求出字符串中的每一个回文串了。

3

仍存在一个值得注意的细节。

我们不妨重新定义一下“翻转”这个词。

不难发现，在第二部分中我们所求的、所描述的一直是“如何求每个字符串的最长半翻转子串？”。

如何求每个字符串 S 的最长全翻转子串呢？这个就非常简单啦，由“全翻转”的定义可知，其最长全翻转子串至多只有一个，而且长度必须是 \left\lfloor\frac{|S|}{2}\right\rfloor，且 |S| 必须是奇数。所以只需要验证一下是否合法即可。

那么“全翻转”和“半翻转”在第一部分有什么体现呢？

不难发现，如果这个字符串 x 想要一步翻转成 S，那么它就可以是“全翻转”，也可以是“半翻转”；但如果这个字符串 x 无法一步翻转成 S，只能翻转到另一个翻转子串 y，那么 x 只能是“半翻转”。

原因是只有在最后一次翻转我们可以砍掉末尾，其他情况下翻转得到的串我们都是要全盘接受的。

4

求回文串？就很简单能想到是 Manacher 算法了。

不会 Manacher 就可以先看看这道题：P3805 【模板】manacher 算法。

在 Manacher 求出了每一个回文串的基础上，我们从后面往前面找每个最长翻转子串。

具体代码作用见注释。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

#define re register 
const int maxn = 1000005;
char st[maxn * 2];
int len[maxn * 2], cnt;
int vis[maxn * 2];
int T;
int mx, po;

inline void input ()
{
    char ch = getchar ();
    st[0] = '~', st[cnt = 1] = '#';
    while (ch < 'a' or ch > 'z') ch = getchar ();
    while (ch >= 'a' and ch <= 'z') st[++cnt] = ch, st[++cnt] = '#', ch = getchar (); 
    st[cnt + 1] = '%';
}

int main ()
{
    scanf ("%d", &T);
    while (T--)
    {
        cnt = mx = po = 0;
        memset (vis, 0, sizeof vis);
        memset (len, 0, sizeof len);
        input ();
        for (re int i (1); i <= cnt; ++i)//Manacher 模板 
        {
            if (i <= mx) len[i] = min (mx - i, len[po * 2 - i]);
            while (st[i + len[i]] == st[i - len[i]]) len[i]++;
            if (i + len[i] > mx) mx = i + len[i] - 1, po = i;
        }
        for (re int i (cnt); i >= 1; --i)
        {
            if (i + len[i] - 1 == cnt) vis[i] = 1;//如果能一次翻转成 
            else if (vis[i + len[i] - 2] and i == len[i]) vis[i] = 1;//如果它能翻转成某个最长翻转子串，如 qwqwq 的 qwqw 的 qw ，且不会越界 
        }
        for (re int i (1); i <= cnt; ++i) if (st[i] >= 'a' and st[i] <= 'z' and vis[i]) printf ("%d ", i / 2);
            //Manacher 处理后的字符串转化成原字符串，长度直接除以 2 就可以得到原字符串的长度 
        printf ("\n");
    }
    return 0;
}

感谢阅读，求赞。

5

回复。