Codeforces 7D. Palindrome Degree

最近在写string 这题manacher和hash各写了一遍

题目链接
乍一看以为是pam 后来发现pam写不了233 不然要写三种的
只要根据dp[i]=dp[i/2]+1;来推就行了 思路还是比较清晰的qwq

manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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("%lld\n",ans);
}
int main(){
scs(s); int len=strlen(s);
manacher(s,len); solve(len);
}

hash

我的hash常数很大啊 抠抠才过
还是seed和mod不公开了吧qwq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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("%lld\n",ans);
}
int main(){
scs(s+1); n=strlen(s+1);
hash_init(); solve();
}