哈希
好用的哈希模数：
- unsigned long long/long long 自然溢出
- \(2654435769\)（存疑）
- \(1610612741\)（极力推荐）
- \(998244353\)，\(10^9+7\)（经典，貌似容易被×）
提供一种 \(N\) 模数哈希的写法：
Luogu P3546
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fd(i,a,b) for(int i=a,_i=b;i<=_i;i=-~i)
#define bd(i,a,b) for(int i=a,_i=b;i>=_i;i=~-i)
using namespace std;
const int N=2e6+509,MT=2;
int n,m,f[N],ans,_L;
char s[N];
inline int read(){int x;scanf("%lld",&x);return x;}
inline void write(int x,int F=1)
{
if(F==0) printf("%lld",x);
else if(F==1) printf("%lld\n",x);
else printf("%lld ",x);
}
struct My_Hash
{
int mod=998244353,seed=131;
int p[N],Pw[N];
inline int Hash(int l,int r) {return ((p[r]-p[l-1]*Pw[r-l+1]%mod+mod)%mod);}
inline void Pre()
{
Pw[0]=1;
fd(i,1,n)
{
p[i]=(p[i-1]*seed+s[i])%mod;
Pw[i]=Pw[i-1]*seed%mod;
}
}
inline void Named(int _mod_,int _seed_) {mod=_mod_,seed=_seed_;}
}H[MT+1];
inline bool Check_Diff(int l,int r,int L,int R)
{
fd(i,0,MT)
if(H[i].Hash(l,r)==H[i].Hash(L,R))
return 0;
return 1;
}
inline bool Check_Same(int l,int r,int L,int R)
{
fd(i,0,MT)
if(H[i].Hash(l,r)!=H[i].Hash(L,R))
return 0;
return 1;
}
signed main()
{
#define FJ
#ifndef FJ
freopen("bzoj1066_.in","r",stdin);
freopen("bzoj1066_.out","w",stdout);
#endif
n=read();m=n/2;
scanf("%s",s+1);
H[0].Named(2654435769,131);//存疑
H[1].Named(1610612741,131);//Good
//998244353 1e9+7//貌似容易被×
/*
// 貌似可以（这道题用这种方法可过）：
srand(time(0));
fd(i,0,MT) H[i].Named((rand()%1000000000)*1000000000+rand()%1000000000,131);
*/
fd(i,0,MT) H[i].Pre();
bd(i,m,0)
{
_L=min(_L+2,m-i);
while(_L>0&&Check_Diff(i+1,i+_L,n-i-_L+1,n-i)) _L--;
if(Check_Same(1,i,n-i+1,n)) ans=max(ans,i+_L);
}
write(ans);
return 0;
}