生活随笔
收集整理的這篇文章主要介紹了
HDU 3068 最长回文
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
最長回文串模板題
Manacher 算法
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #include<cstdlib>
6 #include<
string>
7 #include<cmath>
8 #include<vector>
9 using namespace std;
10 const int maxn=1e5+
7;
11 const double eps=1e-
8;
12 const double pi=acos(-
1);
13 #define ll long long
14 #define clc(a,b) memset(a,b,sizeof(a))
15
16 int Proc(
char pszIn[],
char pszOut[])
17 {
18 int nLen=
1;
19 pszOut[
0]=
'$';
20 int i=
0;
21 while(pszIn[i]!=
'\0')
22 {
23 pszOut[nLen++]=
'#';
24 pszOut[nLen++]=
pszIn[i];
25 i++
;
26 }
27 pszOut[nLen++]=
'#';
28 pszOut[nLen]=
0;
29 return nLen;
30 }
31 void Manacher(
int *p,
char *str,
int len)
32 {
33 int mx=
0,id=
0;
34 for(
int i=
0; i<len; i++
)
35 {
36 p[i]=mx>i?min(p[
2*id-i],mx-i):
1;
37 while(str[i+p[i]]==str[i-p[i]])p[i]++
;
38 if(i+p[i]>
mx)
39 {
40 mx=i+
p[i];
41 id=
i;
42 }
43 }
44 }
45 const int MAXN=
220010;
46 char strIn[MAXN];
47 char strOut[MAXN];
48 int p[MAXN];
49 int main()
50 {
51 while(scanf(
"%s",strIn)!=
EOF)
52 {
53 int nLen=
Proc(strIn,strOut);
54 Manacher(p,strOut,nLen);
55 int ans=
1;
56 for(
int i=
0; i<nLen; i++
)
57 ans=
max(ans,p[i]);
58 printf(
"%d\n",ans-
1);
59 }
60 return 0;
61 }
View Code ?
轉載于:https://www.cnblogs.com/ITUPC/p/5243790.html
總結
以上是生活随笔為你收集整理的HDU 3068 最长回文的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
