HDU 3068 最长回文 【最长回文子串】

和上一题一样,不过这题只是要求最长回文子串的长度

在此采用了非常好用的Manacher算法

据说还是O(n) 的效率QAQ

详细用法参考了上篇博客的参考资料,这两天有空学习一下~

Source code:

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
#define MOD 1000000007
#define pi acos(-1.0) using namespace std; typedef long long ll ;
typedef unsigned long long ull ;
typedef unsigned int uint ;
typedef unsigned char uchar ; template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}
template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;} const double eps = 1e- ;
const int N = ;
const int M = * ;
const ll P = 10000000097ll ; char str[M];//start from index 1
int p[M];
char s[M];
int n; void kp(){
int i;
int mx = ;
int id;
for(i = ; i < n; ++i){
if( mx > i )
p[i] = Min( p[*id-i], p[id]+id-i );
else
p[i] = ;
for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
;
if( p[i] + i > mx ){
mx = p[i] + i;
id = i;
}
}
} void pre(){
int i,j,k;
n = strlen(s);
str[] = '$';
str[] = '#';
for(i = ; i < n; ++i){
str[i* + ] = s[i];
str[i* + ] = '#';
}
n = n* + ;
str[n] = ;
} int main(){
int T,_=, t, i, ans;
while(EOF != scanf("%s", s)){
ans = ;
pre();
kp();
for(i = ; i < n; ++i)
checkmax(ans, p[i]);
printf("%d\n", ans-);
}
return ;
}
上一篇:xxx.properties获取方法


下一篇:Evensgn 的债务