Codeforces 1326D2. Prefix-Suffix Palindrome (Hard version)

比赛睡过去了=。=更一下D2的各种写法

题目链接
manacher hash pam都能搞
upd:kmp也行
思路还是比较清晰的
先把原串分为三部分:前缀 后缀 中间
比如acbba 分成a+cbb+a
然后对中间这个部分找最长的以0开头或者以len-1结尾的回文串
答案就是前缀+最长回文串+后缀

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
36
37
38
#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 = 1e6 + 5;
int che[2*maxn];
string s,ma;
void manacher(string s,int len0){
ma="$#"; rep(i,0,len0) ma+=s[i],ma+='#';
// 别写成ma+=s[i]+'#';了 换成"#"应该就行 呜呜呜血泪教训
int maxx=0,num=0,len=ma.size(); 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(){
cin>>s; int l=0,r=s.size()-1;
while(s[l]==s[r]&&l<r) l++,r--;
string t1=s.substr(0,l),t2=s.substr(r+1);
s=s.substr(l,r-l+1); manacher(s,s.size());
int len=ma.size(),p(0),q(0),r1(0),r2(0);
rep(i,0,len) if(p<che[i]&&i-che[i]<2) p=che[i],r1=i;
dep(i,len-1,0) if(q<che[i]&&i+che[i]==len) q=che[i],r2=i;
// 这部分比较考对manacher数组的熟练?hhh自己手写一下应该就行
if(p>=q) cout<<t1+s.substr(0,p-1)+t2<<'\n';
else cout<<t1+s.substr(s.size()-q+1)+t2<<'\n';
}
int main(){
int _; sc(_); while(_--) solve();
}

hash

还是seed和mod不公开 虽然我这次没有用常用的

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
45
46
#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 = 1e6 + 5;
string s; int n;
int seed,mod,hs1[maxn],hs2[maxn],bas[maxn]; // hs看情况开
void init(int* hs){
s=' '+s; 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;
}
void hash_init(){
seed=?,mod=?; init(hs1);
reverse(s.begin(),s.end()); init(hs2);
}
void solve(){
cin>>s; int l=0,r=s.size()-1,p(0),q(0);
while(s[l]==s[r]&&l<r) l++,r--;
string t1=s.substr(0,l),t2=s.substr(r+1);
s=s.substr(l,r-l+1); n=s.size(); hash_init();
rep(i,1,n+1) if(getsum(hs1,1,i/2)==getsum(hs2,n-i+1,n-(i+1)/2)) p=i;
rep(i,1,n+1) if(getsum(hs2,1,i/2)==getsum(hs1,n-i+1,n-(i+1)/2)) q=i;
if(p>q){
reverse(s.begin(),s.end());
// 现在的s是' '+s+' ' 所以要从1开始
cout<<t1+s.substr(1,p)+t2<<'\n';
} else cout<<t1+s.substr(1,q)+t2<<'\n';
}
int main(){
int _; sc(_); while(_--) solve();
}

pam

呜呜呜好难啊pam好难

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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 = 1e6 + 5;
string s;
struct PAM{
struct node{
int child[26],cnt,fail,num,len,pos;
}tt[maxn];
int last,n,tot;
char s[maxn];
inline void clear(){
rep(i,0,tot+1){
mst(tt[i].child,0);
tt[i].cnt=tt[i].fail=tt[i].len=tt[i].num=tt[i].pos=0;
} last=n=0; tt[0].fail=tot=1; tt[1].len=-1;
}
inline int getfail(int x){
while(s[n-tt[x].len-1]!=s[n]) x=tt[x].fail;
return x;
}
inline void add(char ch){
s[n]=ch;
int cur=getfail(last);
if(!tt[cur].child[ch-'a']){
int now=++tot;
tt[now].len=tt[cur].len+2;
int p=getfail(tt[cur].fail);
tt[now].fail=tt[p].child[ch-'a'];
tt[cur].child[ch-'a']=now;
tt[now].num=tt[tt[now].fail].num+1;
}
last=tt[n].pos=tt[cur].child[ch-'a'];
++tt[last].cnt; ++n;
}
inline void count(){
dep(i,tot,0) tt[tt[i].fail].cnt+=tt[i].cnt;
}
}pam;
int getpos(int n,int l,int r){
int t=pam.tt[r].pos;
while(l*2+pam.tt[t].len>n) t=pam.tt[t].fail;
return pam.tt[t].len;
}
void solve(){
cin>>s; int l=0,r=s.size()-1,n=s.size(),p(0),q(0);
while(s[l]==s[r]&&l<r) l++,r--;
pam.clear(); dep(i,n-1,0) pam.add(s[i]);
p=getpos(n,l,r); reverse(s.begin(),s.end());
pam.clear(); dep(i,n-1,0) pam.add(s[i]);
q=getpos(n,l,r); reverse(s.begin(),s.end());
if(max(p,q)+2*l>=n) cout<<s<<'\n';
else if(p>q) cout<<s.substr(0,p+l)+s.substr(r+1)<<'\n';
else cout<<s.substr(0,l)+s.substr(r-q+1)<<'\n';
}
int main(){
int _; sc(_); while(_--) solve();
}

kmp

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
#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 = 2e6 + 5;
int nex[maxn];
int getnext(string s){
int i=0,j=-1,len=s.size();
nex[0]=-1; while(i<len){
if(j==-1||s[i]==s[j]){
i++; j++; nex[i]=j;
} else j=nex[j];
} return nex[len];
}
void solve(){
string s,t; cin>>s; int l=0,r=s.size()-1;
while(s[l]==s[r]&&l<r) l++,r--;
string t1=s.substr(0,l),t2=s.substr(r+1);
s=s.substr(l,r-l+1); t=s; reverse(t.begin(),t.end());
string a=s+'*'+t,b=t+'*'+s;
string p=a.substr(0,getnext(a));
string q=b.substr(0,getnext(b));
cout<<t1<<(p.size()>q.size()?p:q)<<t2<<'\n';
}
int main(){
int _; sc(_); while(_--) solve();
}