最近在写string 这题manacher和hash各写了一遍
题目链接 乍一看以为是pam 后来发现pam写不了233 不然要写三种的 只要根据dp[i]=dp[i/2] 1;来推就行了 思路还是比较清晰的qwq
manacher
代码语言：javascript复制#include<bits/stdc .h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5e6 5;
char s[maxn],ma[2*maxn];
int che[2*maxn],ww[2*maxn];
void manacher(char* s,int len0){
int len=0; ma[len ]='$'; ma[len ]='#';
rep(i,0,len0) ma[len ]=s[i],ma[len ]='#';
ma[len]=0; int maxx=0,num=0;
rep(i,0,len){
che[i]=maxx>i?min(che[2*num-i],maxx-i):1;
while(ma[i che[i]]==ma[i-che[i]]) che[i] ;
if(i che[i]>maxx) maxx=i che[i],num=i;
}
}
void solve(int len){
ll ans(0); rep(i,1,len 1){
int l=2,r=2*i,m=l r>>1;
if(che[m]*2>r-l 1) ww[r]=ww[m-1-(m-1)%2] 1;
ans =ww[r];
} pf("%lldn",ans);
}
int main(){
scs(s); int len=strlen(s);
manacher(s,len); solve(len);
}hash
我的hash常数很大啊 抠抠才过 还是seed和mod不公开了吧qwq
代码语言：javascript复制#include<bits/stdc .h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5e6 5;
char s[maxn]; int n;
struct haash{
int seed,mod,hs[maxn],bas[maxn]; // hs看情况开
void init(){
bas[0]=1; rep(i,1,n 1){
bas[i]=1ll*bas[i-1]*seed%mod;
hs[i]=1ll*hs[i-1]*seed%mod s[i];
if(hs[i]>=mod) hs[i]-=mod;
}
}
int getsum(int *h,int l,int r){
int res=h[r]-1ll*h[l-1]*bas[r-l 1]%mod;
if(res<0) res =mod;
return res;
}
}hh[2];
void hash_init(){
hh[0].seed=?,hh[0].mod=?; hh[0].init();
reverse(s 1,s n 1);
hh[1].seed=?,hh[1].mod=?; hh[1].init();
}
int ww[maxn];
void solve(){
ll ans=1; ww[1]=1; rep(i,2,n 1){
if(hh[0].getsum(hh[0].hs,1,i/2)==hh[1].getsum(hh[1].hs,n-i 1,n-(i 1)/2))
ww[i]=ww[i/2] 1; ans =ww[i];
} pf("%lldn",ans);
}
int main(){
scs(s 1); n=strlen(s 1);
hash_init(); solve();
}
