自动搬运

查看原文

来自洛谷，原作者为

	pldzy 就像我一直听香夭从未沾湿眼角。

搬运于2025-08-24 22:10:51，当前版本为作者最后更新于2021-08-27 21:54:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Update

• 2024年8月7日：回复 @hzoi_Shadow 的问题“为啥最后判的是i+len[i]-2 而不是 i+len[i]-1”。
• 2025年1月26日：感谢 @small_cabbage 指出文章部分内容叙述有所缺漏，并回复 @small_cabbage 的问题“观察可以发现是怎么观察到的？能否给出严谨证明？”。

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

思路

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

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

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

• “全翻转”：指完全按照题目定义所描述，以字符串 b 的末尾字符为对称中心，将 b 除去末尾字符之外的字符 全部翻转并接到 b 的末尾。
• “半翻转”：指先将字符串 a 进行“全翻转”操作，再从 a 的末尾砍掉若干字符，保证最后得到的新串长度严格大于 a 串长度。

---

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

如何求每个字符串 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

回复。

• 回复 @hzoi_Shadow 的问题“为啥最后判的是i+len[i]-2 而不是 i+len[i]-1”。

  $vis_i$ 定义为 i 作为翻转中心是否合法，且 $S_{i+len_i-1}$ 是特殊字符，所以判的时候判 $vis_{i+len_i-2}$。

• 回复 @small_cabbage 的问题“观察可以发现是怎么观察到的？能否给出严谨证明？”。

  读者自证不难。

  • 命题：一个字符串的半翻转子串是它自己去掉末尾回文串的一半得到。
  • 子命题：一个字符串的最长半翻转子串就是它自己去掉最短末尾回文串的一半。
  • 充分性：显然。可以通过上述举例进行理解。“它自己去掉最短末尾回文串的一半”一定能通过“半翻转”操作得到“它自己”。
  • 必要性：显然。如果这个串 S 能被串 a 通过“半翻转”得到，那么 S-a 这个串一定是 a 除去末尾字符得到的串 a' 的某个真后缀。而也恰恰说明这构成了一个回文串。

  综上所述，一个字符串的半翻转子串是它自己去掉末尾回文串的一半得到，故命题“一个字符串的最长半翻转子串就是它自己去掉最短末尾回文串的一半”成立。