PALINY - Palindrome dài nhất
Tác giả: hieult
Ngôn ngữ: C++
#include <iostream>
#include <vector>
//#include <conio.h>
#include <algorithm>
using namespace std;
int fastFindPalindrome(string &str)
{
int strLength = str.length();
vector<int> vec;
int i = 0;
int palLength = 0;
int Longest = 0;
while(i<strLength)
{
if((i > palLength) && (str[i - palLength - 1] == str[i]) )
{
palLength += 2;
i += 1;
continue;
}
vec.push_back(palLength);
Longest = max (Longest, palLength);
int s = vec.size() -2;
int e = s - palLength;
bool found = false;
for(int j = s; j > e; j--)
{
int d = j -e -1;
if(vec[j]==d)
{
palLength = d;
found = true;
break;
}
vec.push_back(min(d, vec[j]));
Longest = max (Longest, min (d, vec[j]));
}
if(!found)
{
i+=1;
palLength = 1;
}
}
vec.push_back(palLength);
Longest = max (Longest, palLength);
return Longest;
}
int main()
{
string s;
int n;
cin >> n;
cin >> s;
cout << fastFindPalindrome(s);
//getch();
}