hdu3068,hdu3294,回文串,Manacher算法

Posted by Cww97 on 2016-04-04

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/51058578
关于Manacher算法讲解在这
在o(n)时间内算出以每个点为中心的最大回文串长度

hdu3068
模板题

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
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=233333;//20W

int Manacher(string st){
int len=st.size();
int *p=new int[len+1];
memset(p,0,sizeof(p));
int mx=0,id=0;
for (int i=1;i<=len;i++){
if (mx>i)p[i]=min(p[2*id-i],mx-i);
else p[i]=1;
while (st[i+p[i]]==st[i-p[i]])p[i]++;
if (i+p[i]>mx){mx=i+p[i];id=i;}
}
int ma=0;
for(int i=1;i<len;i++)ma=max(ma,p[i]);
delete(p);
return ma-1;
}

int main(){
//freopen("fuck.in","r",stdin);
char st[N];
while (~scanf("%s",st)){
string st0="$#";
for (int i=0;st[i]!='\0';i++){
st0+=st[i]; st0+="#";
}
printf("%d\n",Manacher(st0));
}
return 0;
}

hdu3294
最后输出的时候稍微处理一下就好

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
#include<map>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200400;
string ans;
int _start,_end;

int Manacher(string st){
int len=st.size();
int *p=new int[len+1];
memset(p,0,sizeof(p));
int mx=0,id=0;
for (int i=1;i<=len;i++){
if (mx>i)p[i]=min(p[id*2-i],mx-i);
else p[i]=1;
while (st[i+p[i]]==st[i-p[i]])p[i]++;
if (i+p[i]>mx)mx=i+p[i],id=i;
}
int ma=0,ii;
for (int i=1;i<len;i++)
if (p[i]>ma)ma=p[i],ii=i;
ma--;
_start=((ii-ma+1)>>1)-1;
_end =((ii+ma-1)>>1)-1;
ans="";
for (int i=ii-ma;i<=ii+ma;i++)
if (st[i]!='#')ans+=st[i];
delete(p);
return ma;
}

void writeln(char ch,string st){
char tag='a'-1;
map<char,char>t;
for (char i=ch;i<='z';i++)t[i]=++tag;
for (char i='a';i< ch;i++)t[i]=++tag;
int len=st.size();
printf("%d %d\n",_start,_end);
for (int i=0;i<len;i++)printf("%c",t[st[i]]);
puts("");
}

int main(){
char ch,st[N];
while (~scanf("%c %s\n",&ch,st)){
string st0="$#";
for (int i=0;st[i]!='\0';i++)
{st0+=st[i];st0+="#";}
if (Manacher(st0)==1)puts("No solution!");
else writeln(ch,ans);
}
return 0;
}

明天高数月考,,,,求rp++