【Mili】world.execute(me);
咋是我最不会的字符串啊。呜呜呜根本不会各种板子。
留着以后巩固完各类字符串板子再接着写吧。
[POI 2012] PRE-Prefixuffix
题意
对于两个字符串 \(S_1,S_2\)，如果能将 \(S_1\) 的一个后缀移动到开头使 \(S_1\) 变成 \(S_2\)，就称 \(S_1\) 与 \(S_2\) 循环同构。
给定一个字符串 \(S\)，找到一个长度 \(L\le \frac{\lvert S\rvert}{2}\)，使得 \(S\) 长度为 \(L\) 的前缀与长度为 \(L\) 的后缀循环同构。
\(1\le \lvert S\rvert \le 10^6\)。
solution
两个字符串循环同构当且仅当它们分别可以写成 \(AB\) 和 \(BA\) 的形式，那么我们可以考虑 \(S\) 的每个 Border，用它的长度加上将其删去后得到字符串的最长 Border 长度更新答案，那么如何求这个字符串删去一个前缀和一个后缀后得到新字符串的最长 Border 长度呢？
考虑从中间依次加入元素，维护 \(p\) 表示当前字符串长度不大于当前长度一半的最长 Border 长度，发现每在左右各加入一个元素，\(p\) 至多增加 \(2\)，那么每次加入时我们直接令 \(p\leftarrow p+2\)，然后判断 \(p\) 是否满足上述条件，不满足就 \(p\leftarrow p-1\)，直到满足为止，这样就能求出删去一个前缀和后缀后新字符串最长 Border，由于 \(p\) 每次最多增加 \(2\)，那么复杂度均摊 \(O(n)\)。
然后枚举原字符串的每个 Border 并更新答案即可，判断长度为 \(p\) 的前缀是否是 Border 可以直接用哈希，后面枚举 Border 时也可以直接哈希，不用写 KMP。
时间复杂度 \(O(n)\)。
还有一种做法是构造字符串 $s_1s_ns_2s_{n-1}s_3s_{n-2}\dots $，那么转化为求 最长双回文串，感觉这个构造比较反直觉感兴趣可以去看题解，时间复杂度同样是 \(O(n)\)，这里不多介绍。
Code
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=1e6+10;
constexpr int inf=1e6+10;inline void read(int &x) {x=0;char ch=getchar();while (ch<48) ch=getchar(); while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}int n,ans;
int f[N];
char s[N];struct Hash {int B,M;ll mp[N],fac[N];inline void get_Hash(int _B,int _M) {B=_B;M=_M;fac[0]=1;f(i,1,n) fac[i]=fac[i-1]*B%M,mp[i]=(mp[i-1]*B+s[i]-'a'+1)%M;}inline ll H(int l,int r) {return (mp[r]-mp[l-1]*fac[r-l+1]%M+M)%M;}
}H1,H2;
inline bool check(int l1,int r1,int l2,int r2) {return (H1.H(l1,r1)==H1.H(l2,r2))&&(H2.H(l1,r1)==H2.H(l2,r2));}int main() {read(n);scanf("%s",s+1);H1.get_Hash(131,1e9+97);H2.get_Hash(31,998244853);int l=n/2,r=n/2+1+(n&1),now=-1,mx=n/2;while (l) {now+=2;while (l+now-1>=r-now+1) now--;while (now&&!check(l,l+now-1,r-now+1,r)) now--;f[l]=now;l--;r++;}f(i,1,mx) if (check(1,i,n-i+1,n)) ans=max(ans,i+f[i+1]);printf("%d\n",ans);return 0;
}