У информатици, проблем најдужег палиндрома у стрингу или највећи симетрични фактор је проблем налажења најдужег подстринга датог стринга, подстринг мора бити палиндром. На пример, најдужи палиндром у речи "банана" је "анана". Најдужи палиндром не мора бити јединствен; на пример, у стрингу "абракадабра", не постоји палиндром који има више од три слова, али постоје два палиндрома са дужином три, конкретно, "ака" и "ада". У неким применама је потребно вратити све највеће палиндроме (односно, све подстрингове који су палиндроми и не могу бити проширени а да притом задрже својство палиндрома) уместо враћања само једног од најдужих палиндрома или дужине највећег палиндрома у оквиру стринга..
Глен Манакер 1975 је нашао алгоритам у линеарном времену за листање свих палиндрома који се појављују на почетку стринга. Међутим, Apostolico, Breslauer & Galil 1995, су приметили да се исти алгоритам може употребити за налажење највећих палиндрома у стрингу, небитно од позиције палиндрома, опет у линеарном времену. Дакле, пружа решење на проблем налажења најдужег палиндрома у стрингу у линеарном времену. Алтернативно решење које се такође извршава у линеарном времену су пружили Jeuring 1994 и Gusfield 1997, који су описали решење засновано на суфиксном стаблу. Познат је и ефикасни паралелни алгоритам за овај проблем.[1]
Најдужи палиндром у стрингу не сме бити помешан са другим проблемом налажења најдужег подскупа који задовољава својство палиндрома. Подскуп стринга иако задовољава својство, у опису проблема, да се карактери појављују у растућем редоследу (у смислу први члан подскупа се сигурно појављује пре другог и тако редом) не подразумева се да су чланови подскупа УЗАСТОПНИ, што је услов код најдужег палиндрома у стрингу.
Да би нашли у линеарном времену најдужи палиндром у стрингу, алгоритам користи одређене карактеристике и закључке о палиндромима и под-палиндормима (у овом контексту палиндром са тенденцијом раста, на пример реч "ада" може се проширити у "радар"):
Нека је:
#include <string>
#include <vector>
#include <iostream>
std::vector<char> addBoundaries(std::vector<char> cs) {
if(cs.size() == 0){
std::vector<char> cs2;
cs2.push_back('|');
cs2.push_back('|');
return cs2;
}
std::vector<char> cs2(cs.size()* 2 + 1);
for(int i = 0; i < (cs2.size() - 1); i += 2) {
cs2[i] = '|';
cs2[i+1] = cs[i/2];
}
cs2[cs2.size()-1] = '|';
return cs2;
}
std::vector<char> removeBoundaries(std::vector<char> cs) {
if(cs.size() < 3) {
std::vector<char> cs2;
return cs2;
}
std::vector<char> cs2((cs.size()-1)/2);
for (int i = 0; i < cs2.size(); ++i) {
cs2[i] = cs[i*2+1];
}
return cs2;
}
std::string findLongestPalindrome(std::string s) {
if(s.length() == 0)
return "";
std::vector<char> temp(s.begin(),s.end());
std::vector<char> s2 = addBoundaries(temp);
std::vector<int> p(s2.size());
int c = 0, r = 0; // Here the first element in s2 has been processed.
int m = 0, n = 0; // The walking indices to compare if two elements are the same
for(int i = 1; i < s2.size(); i++) {
if(i > r) {
p[i] = 0;
m = i - 1;
n = i + 1;
}
else {
int i2 = c * 2 - i;
if(p[i2] < (r - i)) {
p[i] = p[i2];
m = -1; // This signals bypassing the while loop below.
}
else {
p[i] = r - i;
n = r + 1;
m = i * 2 -n;
}
}
while(m >= 0 && n < s2.size() && s2[m] == s2[n]){
p[i]++;
m--;
n++;
}
if((i+p[i]) > r) {
c = i;
r = i + p[i];
}
}
int len = 0;
c = 0;
for(int i = 1; i < s2.size(); ++i) {
if(len < p[i]) {
len = p[i];
c = i;
}
}
std::vector<char> temp1(s2.begin() + (c - len), s2.begin() + (c + len + 1));
std::vector<char> ss = removeBoundaries(temp1);
return std::string(ss.begin(), ss.end());
}
import java.util.Arrays;
public class ManachersAlgorithm {
public static String findLongestPalindrome(String s) {
if (s==null || s.length()==0)
return "";
char[] s2 = addBoundaries(s.toCharArray());
int[] p = new int[s2.length];
int c = 0, r = 0; // Here the first element in s2 has been processed.
int m = 0, n = 0; // The walking indices to compare if two elements are the same
for (int i = 1; i<s2.length; i++) {
if (i>r) {
p[i] = 0; m = i-1; n = i+1;
} else {
int i2 = c*2-i;
if (p[i2]<(r-i)) {
p[i] = p[i2];
m = -1; // This signals bypassing the while loop below.
} else {
p[i] = r-i;
n = r+1; m = i*2-n;
}
}
while (m>=0 && n<s2.length && s2[m]==s2[n]) {
p[i]++; m--; n++;
}
if ((i+p[i])>r) {
c = i; r = i+p[i];
}
}
int len = 0; c = 0;
for (int i = 1; i<s2.length; i++) {
if (len<p[i]) {
len = p[i]; c = i;
}
}
char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
return String.valueOf(removeBoundaries(ss));
}
private static char[] addBoundaries(char[] cs) {
if (cs==null || cs.length==0)
return "||".toCharArray();
char[] cs2 = new char[cs.length*2+1];
for (int i = 0; i<(cs2.length-1); i = i+2) {
cs2[i] = '|';
cs2[i+1] = cs[i/2];
}
cs2[cs2.length-1] = '|';
return cs2;
}
private static char[] removeBoundaries(char[] cs) {
if (cs==null || cs.length<3)
return "".toCharArray();
char[] cs2 = new char[(cs.length-1)/2];
for (int i = 0; i<cs2.length; i++) {
cs2[i] = cs[i*2+1];
}
return cs2;
}
}