P5446 [THUPC2018]绿绿和串串 题解

学校字符串考试的题，唯一一道 \(100\,pts\) 的，于是就来写TJ了（

1.题意

给定一个字符串 \(S\) ，判断 \(S\) 的前缀中有哪些长度满足将其以尾字符为轴翻转后可以覆盖 \(S\) 并输出.

举个粒子，标红的字符为翻转轴：
对于串 \(S= \tt aabaaab\) 的前缀 \(\tt aab\) ，经过第一次翻转： \(\tt aa\color{red}b\color{black}aa\) ，不能覆盖 \(S\) ，再将这个串翻转，得到 \(\tt aaba\color{red}a\color{black}abaa\) ，这时发现它覆盖了 \(S\) ，所以长度 \(3\) 是合法的.

2.解析

看到翻转，马上想到这是考回文串的
看到回文串，马上想到了 \(\tt Manacher\)
但是，怎么利用 \(\tt Manacher\) ？
不难发现，以某个字符为轴翻转后，就形成了一个以它为轴的回文串，而以某个字符为轴的回文串的长度正好就是 \(\tt Manacher\) 要求的东西.

怎么判断它翻转过后是合法的呢？
考虑 \(\tt Manacher\) 求得回文串长时的结束条件: 指针指向的两个字符不相等，
也就是说，以某个位置为轴将左边的字符串（反向）和右边的字符串匹配时，在两个指针分别指向的位置失配了.
这个又有什么用呢？我们可以拿它来判断翻转过后是否合法！
合法的情况只有一种，就是这两个指针中的一个指向了空位置.而空位置只有两个： \(S\) 左边界的左边和 \(S\) 右边界的右边.
也就是说，只有回文左边界等于 \(S\) 左边界或者回文右边界等于 \(S\) 右边界的位置可能构成答案.
然后，我们要做的就是判断这些位置是否可以构成答案.

我们这里先假定字符串下标从 \(1\) 开始.
对于前缀 \(S_{1,x}\) ，分以下两种情况：

• 1.将它进行 \(1\) 次翻转后就可以覆盖 \(S\) .
  这种情况下，它在 \(\tt Manacher\) 中跑出的回文串右边界一定等于 \(S\) 的右边界.因为这说明，在它的回文左边界更左边的字符，对称过后一定在 \(S\) 整个串的右边，可以忽略；而其它的字符构成以 \(x\) 为轴的回文串，所以对它做 \(1\) 次翻转就可以覆盖 \(S\) .
• 2.将它进行 \(1\) 次翻转后不能覆盖 \(S\) .
  这种情况很好办，如果回文左边界不是 \(S\) 左边界，那么它就一定不能满足条件，直接否决它.
  如果回文左边界是 \(S\) 左边界，那么我们可以直接跳跃到它的回文右边界，然后再进行判断，直到满足情况 \(1\) 或是被否决.

整体做法就是上面这样.

（如果您看到这里已经有了思路，您可以跳过以下内容）
有些同志可能对回文左/右边界比较迷惑，因为我考场上思考的时候比较乱，所以选定的回文边界比较奇特
这里作一点解释:
\(\tt Manacher\) 算法中，我们首先把要处理的字符串变成一个添加了无关字符的长串，然后再求解每个位置为轴的回文串长度.
那么，对于每个位置，我们就求得了以它为轴的回文串的左边界和右边界.
注意这里的左边界和右边界并不是我们的回文左/右边界！回文左/右边界是左（右）边界的右（左）边一个的位置，因为左右边界对应的字符一定是 \(\tt \#\) （或者其它添加的无关字符），所以我们把它们往左右推进一位，得到对应着原串 \(S\) 中字符的边界.
对应到代码中就是：

x的回文左边界: x-Rel[x]+2
x的回文右边界: x+Rel[x]-2

那么上面的思路也就不难理解了

3.Code

其实是考场代码，删除了奇奇怪怪的注释,对代码作用写了一点注释，并且做了一点点可读化处理.

#include 
#define ri register int
#define MAXN 3000001 //Manacher记得开两倍……
#define ll long long
using namespace std;

int T,lens;
string s;
int Rel[MAXN];

inline void Sync(){
	ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
}

inline void Manacher(){
    lens=s.length();
    string buf="%#";
    for(ri i=0;iMxr)
        Mxr=i+Rel[i],ind=i;
    }
} //就是普通的Manacher，放到模板题也能用((( 

#define reset(x,i) memset(x,i,sizeof(x))
int main()
{
    Sync(); //Sync With Me !
    cin>>T;
    while(T--){
        reset(Rel,0); //清空Manacher数组 
        cin>>s;
        Manacher(); //跑Manacher 
        for(ri i=2;i2&&j+Rel[j]<=lens;j+=Rel[j]-2){ //Rel[j]>2限制了回文串长度必须大于1 
                if(j+Rel[j]==lens){ //对应情况1：回文右边界和串右边界相等 
                    f=1; //标记答案 
					break; //直接退出去输出 
				}
                if(j-Rel[j]>2&&j+Rel[j]