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} ，分以下两种情况：

整体做法就是上面这样.

（如果您看到这里已经有了思路，您可以跳过以下内容）
有些同志可能对回文左/右边界比较迷惑，因为我考场上思考的时候比较乱，所以选定的回文边界比较奇特
这里作一点解释:

那么，对于每个位置，我们就求得了以它为轴的回文串的左边界和右边界. 注意这里的左边界和右边界并不是我们的回文左/右边界！回文左/右边界是左（右）边界的右（左）边一个的位置，因为左右边界对应的字符一定是 $\tt \#$ （或者其它添加的无关字符），所以我们把它们往左右推进一位，得到对应着原串 $S$ 中字符的边界. 对应到代码中就是： ```cpp x的回文左边界: x-Rel[x]+2 x的回文右边界: x+Rel[x]-2 ``` 那么上面的思路也就~~不难理解了~~ ## 3.Code 其实是考场代码，删除了~~奇奇怪怪的~~注释,对代码作用写了一点注释，并且做了一点点可读化处理. ```cpp #include <bits/stdc++.h> #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;i<lens;i++) buf+=s[i],buf+="#"; lens=buf.length(); ri ind=0,Mxr=0; for(ri i=2,j;i<lens;i+=2){ j=(ind<<1)-i; Rel[i]=(i<Mxr?min(Rel[j],Mxr-i):1); while(buf[i+Rel[i]]==buf[i-Rel[i]]) ++Rel[i]; if(i+Rel[i]>Mxr) Mxr=i+Rel[i],ind=i; } } //就是普通的Manacher，跳的时候跳2个就行 #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;i<lens-2;i+=2){ //lens-2是最后一个非'#'字符 register bool f=0; for(ri j=i;Rel[j]>2&&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]<lens) //如果对称后不匹配 break; //直接退出 } if(f) //有答案，输出 cout<<i/2<<" "; //Manacher串中下标为i，对应S中下标为i/2 } cout<<s.length()<<endl; //别忘了所有的S都可以作为初始串 } return 0; } ``` 然后就做完辣！