题目1252：回文子串
- 题目描述：
-
输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
- 输入：
-
存在多组数据，每组数据一行字符串，长度不大于100。
- 输出：
-
输出回文子串的最大长度。
- 样例输入：
-
google
- 样例输出：
-
4
算法分析
另外一种错位比较法 参见 1252：回文子串
源程序
//============================================================================
// Name : judo1252Manacher.cpp
// Author : wdy
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
void Manach(std::string &s){
std::vector<char> ns;
ns.push_back('$');
ns.push_back('#');
int len = s.size();
for(int i = 0;i<len;i++){// become odd
ns.push_back(s.at(i));
ns.push_back('#');
}
len = ns.size();
int *mLen = new int[len]; //record max radius of sub string in the middle of id
int mx = 0;
int id = 0;
int maxLen = 0;
for(int i = 0;i<len;i++){
mLen[i] = 1;
if(mx>i){
mLen[i] = max(mLen[2*id-i],mx-i+1);
}
while((i+mLen[i])<len && i-mLen[i]>0 && ns.at(i+mLen[i])==ns.at(i-mLen[i]))
mLen[i]++;
if(i + mLen[i]-1 >mx){ //update mx,id
mx = i + mLen[i]-1 >mx;
id = i;
}
if(mLen[i]>maxLen) //update maxLen
maxLen = mLen[i];
}
std::cout<<maxLen-1<<std::endl;
}
void judo(){
std::string s;
while(std::cin>>s){
Manach(s);
}
}
int main() {
judo();
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
return 0;
}
/**************************************************************
Problem: 1252
User: KES
Language: C++
Result: Accepted
Time:0 ms
Memory:1520 kb
****************************************************************/