например, "ccddcc" в строке "abaccddccefe"
Я думал о решении, но он работает в O (n ^ 2) времени
Algo 1:
Шаги: Его метод грубой силы
Вопросы: 1. Этот алгоритм проходит в O (n ^ 2) раз.
Algo 2:
Можете ли вы, ребята, подумать об алго, который работает в лучшем случае. Если возможно O (n) время
Вы можете найти самый длинный палиндром, используя алгоритм Manacher в O(n) раз! Его реализацию можно найти здесь и здесь.
Для ввода String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" он находит правильный результат, который равен 1234567887654321.
Algo 2 может не работать для всех строк. Вот пример такой строки "ABCDEFCBA".
Не то, чтобы строка имела "ABC" и "CBA" в качестве подстроки. Если вы измените исходную строку, это будет "ABCFEDCBA". и самая длинная совпадающая подстрока - это "ABC", которая не является палиндром.
Вам может потребоваться дополнительно проверить, является ли эта длинная совпадающая подстрока фактически палиндром, который имеет время работы O (n ^ 3).
Насколько я понял эту проблему, мы можем находить палиндромы вокруг центрального индекса и охватывать наш поиск в обоих направлениях, справа и слева от центра. Учитывая, что, зная, что на углах ввода нет палиндрома, мы можем установить границы на 1 и длину-1. Обращая внимание на минимальную и максимальную границы String, мы проверяем, совпадают ли символы в положениях симметричных индексов (справа и слева) для каждого центрального положения, пока мы не достигнем нашего максимального верхнего граничного центра.
Внешний цикл - O (n) (max n-2 итерации), а внутренний цикл while - O (n) (max вокруг (n/2) - 1 итераций)
Здесь моя реализация Java, используя пример, предоставленный другими пользователями.
class LongestPalindrome {
/**
* @param input is a String input
* @return The longest palindrome found in the given input.
*/
public static String getLongestPalindrome(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex - 1; rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome.length() ? currentPalindrome : longestPalindrome;
leftIndex--; rightIndex++;
}
}
return longestPalindrome;
}
public static void main(String ... args) {
String str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
String longestPali = getLongestPalindrome(str);
System.out.println("String: " + str);
System.out.println("Longest Palindrome: " + longestPali);
}
}
Результатом этого является следующее:
marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321
с регулярным выражением и рубином вы можете сканировать короткие палиндромы следующим образом:
PROMPT> irb
>> s = "longtextwithranynarpalindrome"
=> "longtextwithranynarpalindrome"
>> s =~ /((\w)(\w)(\w)(\w)(\w)\6\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\w\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)\w\4\3\2)/; p $1
"ranynar"
=> nil
Мне недавно задали этот вопрос. Вот решение, которое я [в конечном итоге] придумал. Я сделал это в JavaScript, потому что это довольно просто на этом языке.
Основная концепция заключается в том, что вы просматриваете строку, которая ищет мельчайший многосимвольный палиндром (либо двух, либо трехзначный). Как только вы это сделаете, разверните границы с обеих сторон, пока не перестанет быть палиндром. Если эта длина длиннее самой длинной, сохраните ее и двигайтесь вперед.
// This does the expanding bit.
function getsize(s, start, end) {
var count = 0, i, j;
for (i = start, j = end; i >= 0 && j < s.length; i--, j++) {
if (s[i] !== s[j]) {
return count;
}
count = j - i + 1; // keeps track of how big the palindrome is
}
return count;
}
function getBiggestPalindrome(s) {
// test for simple cases
if (s === null || s === '') { return 0; }
if (s.length === 1) { return 1; }
var longest = 1;
for (var i = 0; i < s.length - 1; i++) {
var c = s[i]; // the current letter
var l; // length of the palindrome
if (s[i] === s[i+1]) { // this is a 2 letter palindrome
l = getsize(s, i, i+1);
}
if (i+2 < s.length && s[i] === s[i+2]) { // 3 letter palindrome
l = getsize(s, i+1, i+1);
}
if (l > longest) { longest = l; }
}
return longest;
}
Это может быть определенно очищено и оптимизировано немного больше, но оно должно иметь довольно хорошую производительность во всех, кроме наихудшего сценария (строка одной и той же буквы).
Привет Вот мой код, чтобы найти самый длинный палиндром в строке. Пожалуйста, обратитесь к следующей ссылке, чтобы понять алгоритм http://stevekrenzel.com/articles/longest-palnidrome
Используемые тестовые данные: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
//Function GetPalindromeString
public static string GetPalindromeString(string theInputString)
{
int j = 0;
int k = 0;
string aPalindrome = string.Empty;
string aLongestPalindrome = string.Empty ;
for (int i = 1; i < theInputString.Length; i++)
{
k = i + 1;
j = i - 1;
while (j >= 0 && k < theInputString.Length)
{
if (theInputString[j] != theInputString[k])
{
break;
}
else
{
j--;
k++;
}
aPalindrome = theInputString.Substring(j + 1, k - j - 1);
if (aPalindrome.Length > aLongestPalindrome.Length)
{
aLongestPalindrome = aPalindrome;
}
}
}
return aLongestPalindrome;
}
Эффективное решение Regexp, которое позволяет избежать грубой силы
Запускает всю длину строки и работает до двух символов, существует, как только будет выполнено совпадение
Для "abaccddccefe" перед возвращением ccddcc повторяются 7 регулярных выражений 7.
(.) (.) (.) (.) (.) (.) (\ 6) (\ 5) (\ 4) (\ 3) (\ 2) (\ 1)
(.) (.) (.) (.) (.) (.) (\ 5) (\ 4) (\ 3) (\ 2) (\ 1)
(.) (.) (.) (.) (.) (\ 5) (\ 4) (\ 3) (\ 2) (\ 1)
(.) (.) (.) (.) (.) (\ 4) (\ 3) (\ 2) (\ 1)
(.) (.) (.) (.) (\ 4) (\ 3) (\ 2) (\ 1)
(.) (.) (.) (.) (\ 3) (\ 2) (\ 1)
(.) (.) (.) (\ 3) (\ 2) (\ 1)
Dim strTest
wscript.echo Palindrome("abaccddccefe")
Sub Test()
Dim strTest
MsgBox Palindrome("abaccddccefe")
End Sub
функция
Function Palindrome(strIn)
Set objRegex = CreateObject("vbscript.regexp")
For lngCnt1 = Len(strIn) To 2 Step -1
lngCnt = lngCnt1 \ 2
strPal = vbNullString
For lngCnt2 = lngCnt To 1 Step -1
strPal = strPal & "(\" & lngCnt2 & ")"
Next
If lngCnt1 Mod 2 = 1 Then strPal = "(.)" & strPal
With objRegex
.Pattern = Replace(Space(lngCnt), Chr(32), "(.)") & strPal
If .Test(strIn) Then
Palindrome = .Execute(strIn)(0)
Exit For
End If
End With
Next
End Function
Смотрите статью Википедии по этой теме. Пример Алгоритм Manacher Реализация Java для линейного решения O (n) из следующей статьи:
импортировать java.util.Arrays; открытый класс 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; } }
Я написал следующую программу Java из любопытства, простой и понятной HTH. Спасибо.
/**
*
* @author sanhn
*/
public class CheckPalindrome {
private static String max_string = "";
public static void checkSubString(String s){
System.out.println("Got string is "+s);
for(int i=1;i<=s.length();i++){
StringBuilder s1 = new StringBuilder(s.substring(0,i));
StringBuilder s2 = new StringBuilder(s.substring(0,i));
s2.reverse();
if(s1.toString().equals(s2.toString())){
if(max_string.length()<=s1.length()){
max_string = s1.toString();
System.out.println("tmp max is "+max_string);
}
}
}
}
public static void main(String[] args){
String s="HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE";
for(int i=0; i<s.length(); i++)
checkSubString(s.substring(i, s.length()));
System.out.println("Max string is "+max_string);
}
}
Попробуйте строку - "HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE"; Он должен работать для четных и нечетных друзей. Огромное спасибо Мохиту!
с использованием пространства имен std;
string largestPal(string input_str)
{
string isPal = "";
string largest = "";
int j, k;
for(int i = 0; i < input_str.length() - 1; ++i)
{
k = i + 1;
j = i - 1;
// starting a new interation
// check to see if even pal
if(j >= 0 && k < input_str.length()) {
if(input_str[i] == input_str[j])
j--;
else if(input_str[i] == input_str[j]) {
k++;
}
}
while(j >= 0 && k < input_str.length())
{
if(input_str[j] != input_str[k])
break;
else
{
j--;
k++;
}
isPal = input_str.substr(j + 1, k - j - 1);
if(isPal.length() > largest.length()) {
largest = isPal;
}
}
}
return largest;
}
Следующий код вычисляет Palidrom для строк длины и нечетной длины.
Не лучшее решение, но работает для обоих случаев
HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE
private static String getLongestPalindrome(String string) {
String odd = getLongestPalindromeOdd(string);
String even = getLongestPalindromeEven(string);
return (odd.length() > even.length() ? odd : even);
}
public static String getLongestPalindromeOdd(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex;
rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome
.length() ? currentPalindrome : longestPalindrome;
leftIndex--;
rightIndex++;
}
}
return longestPalindrome;
}
public static String getLongestPalindromeEven(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex - 1;
rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome
.length() ? currentPalindrome : longestPalindrome;
leftIndex--;
rightIndex++;
}
}
return longestPalindrome;
}
Мы можем найти все палиндромы всей длины, используя это.
Пример:
word = abcdcbc
modifiedString = a # b # С# d # С# b # c
palinCount = 1010105010301
длина самого длинного палиндрома = 5;
длинный палиндром = bcdcb
открытый класс MyLongestPalindrome {
static String word;
static int wordlength;
static int highestcount = 0;
static int newlength;
static char[] modifiedString; // stores modified string
static int[] palinCount; // stores palindrome length at each position
static char pound = '#';
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
System.out.println("Enter String : ");
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader bfr = new BufferedReader(isr);
word = bfr.readLine();
wordlength = word.length();
newlength = (wordlength * 2) - 1;
convert();
findpalindrome();
display();
}
// Inserting # in string
public static void convert() {
modifiedString = new char[newlength];
int j = 0;
int i;
for (i = 0; i < wordlength - 1; i++) {
modifiedString[j++] = word.charAt(i);
modifiedString[j++] = pound;
}
modifiedString[j] = word.charAt(i);
}
// display all palindromes of highest length
public static void display() {
String palindrome;
String s = new String(modifiedString);
System.out.println("Length of longest palindrome = " + highestcount);
for (int i = 0; i < newlength; i++) {
if (palinCount[i] == highestcount) {
palindrome = s.substring(i - (highestcount - 1), i
+ (highestcount));
i = i + (highestcount - 1);
palindrome = palindrome.replace("#", "");
System.out.println(palindrome);
}
}
}
// populate palinCount with length of palindrome string at each position
public static void findpalindrome() {
int left, right, count;
palinCount = new int[newlength];
palinCount[0] = 1;
palinCount[newlength - 1] = 1;
for (int i = 1; i < newlength - 1; i++) {
count = 0;
left = i - 1;
right = i + 1;
;
if (modifiedString[i] != pound)
count++;
while (left >= 0 && right < newlength) {
if (modifiedString[left] == modifiedString[right]) {
if (modifiedString[left] != pound)
count = count + 2;
left--;
right++;
} else
break;
}
palinCount[i] = count;
highestcount = count > highestcount ? count : highestcount;
}
}
}
Здесь я написал логику, попробую:)
public class palindromeClass{
public static String longestPalindromeString(String in) {
char[] input = in.toCharArray();
int longestPalindromeStart = 0;
int longestPalindromeEnd = 0;
for (int mid = 0; mid < input.length; mid++) {
// for odd palindrome case like 14341, 3 will be the mid
int left = mid-1;
int right = mid+1;
// we need to move in the left and right side by 1 place till they reach the end
while (left >= 0 && right < input.length) {
// below check to find out if its a palindrome
if (input[left] == input[right]) {
// update global indexes only if this is the longest one till now
if (right - left > longestPalindromeEnd
- longestPalindromeStart) {
longestPalindromeStart = left;
longestPalindromeEnd = right;
}
}
else
break;
left--;
right++;
}
// for even palindrome, we need to have similar logic with mid size 2
// for that we will start right from one extra place
left = mid;
right = mid + 1;// for example 12333321 when we choose 33 as mid
while (left >= 0 && right < input.length)
{
if (input[left] == input[right]) {
if (right - left > longestPalindromeEnd
- longestPalindromeStart) {
longestPalindromeStart = left;
longestPalindromeEnd = right;
}
}
else
break;
left--;
right++;
}
}
// we have the start and end indexes for longest palindrome now
return in.substring(longestPalindromeStart, longestPalindromeEnd + 1);
}
public static void main(String args[]){
System.out.println(longestPalindromeString("HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE"));
}
}
Для линейного решения вы можете использовать алгоритм Манахера. Существует еще один алгоритм, называемый Gusfield Algorithm, а ниже - код в java:
public class Solution {
char[] temp;
public int match(int a, int b,int len){
int i = 0;
while (a-i>=0 && b+i<len && temp[a-i] == temp[b+i]) i++;
return i;
}
public String longestPalindrome(String s) {
//This makes use of the assumption that the string has not more than 1000 characters.
temp=new char[1001*2];
int[] z=new int[1001 * 2];
int L=0, R=0;
int len=s.length();
for(int i=0;i<len*2+1;i++){
temp[i]='.';
}
for(int i=0;i<len;++i){
temp[i*2+1] = s.charAt(i);
}
z[0]=1;
len=len*2+1;
for(int i=0;i<len;i++){
int ii = L - (i - L);
int n = R + 1 - i;
if (i > R)
{
z[i] = match(i, i,len);
L = i;
R = i + z[i] - 1;
}
else if (z[ii] == n)
{
z[i] = n + match(i-n, i+n,len);
L = i;
R = i + z[i] - 1;
}
else
{
z[i] = (z[ii]<= n)? z[ii]:n;
}
}
int n = 0, p = 0;
for (int i=0; i<len; ++i)
if (z[i] > n)
n = z[p = i];
StringBuilder result=new StringBuilder();
for (int i=p-z[p]+1; i<=p+z[p]-1; ++i)
if(temp[i]!='.')
result.append(String.valueOf(temp[i]));
return result.toString();
}
}
Вы можете найти больше о других решениях, таких как лучшее решение O (n ^ 2) или алгоритм Manacher из мой собственный блог.
Это вернет длинную строку палиндрома из заданной строки
-(BOOL)isPalindromString:(NSString *)strInput
{
if(strInput.length<=1){
return NO;
}
int halfLenth = (int)strInput.length/2;
BOOL isPalindrom = YES;
for(NSInteger i=0; i<halfLenth; i++){
char a = [strInput characterAtIndex:i];
char b = [strInput characterAtIndex:(strInput.length-1)-i];
if(a != b){
isPalindrom = NO;
break;
}
}
NSLog(@"-%@- IS Plaindrom %@",strInput,(isPalindrom ? @"YES" : @"NO"));
return isPalindrom;
}
-(NSString *)longestPalindrom:(NSString *)strInput
{
if(strInput.length<=1){
return @"";
}
NSString *strMaxPalindrom = @"";
for(int i = 0; i<strInput.length ; i++){
for(int j = i; j<strInput.length ; j++){
NSString *strSub = [strInput substringWithRange:NSMakeRange(i, strInput.length-j)];
if([self isPalindromString:strSub]){
if(strSub.length>strMaxPalindrom.length){
strMaxPalindrom = strSub;
}
}
}
}
NSLog(@"-Max - %@",strMaxPalindrom);
return strMaxPalindrom;
}
-(void)test
{
[self longestPalindrom:@"abcccbadeed"];
}
== OUTPUT ===
Вход: abcccde Выход: ccc
Вход: abcccbd Выход: bcccb
Вход: abedccde Выход: edccde
Вход: abcccdeed Выход: документ
Вход: abcccbadeed Выход: abcccba
Здесь реализация в javascript:
var longestPalindromeLength = 0;
var longestPalindrome = ''
function isThisAPalidrome(word){
var reverse = word.split('').reverse().join('')
return word == reverse
}
function findTheLongest(word){ // takes a word of your choice
for(var i = 0; i < word.length; i++){ // iterates over each character
var wordMinusOneFromBeginning = word.substr(i, word.length) // for each letter, create the word minus the first char
for(var j = wordMinusOneFromBeginning.length; j > 0; j--){ // for the length of the word minus the first char
var wordMinusOneFromEnding = wordMinusOneFromBeginning.substr(0, j) // create a word minus the end character
if(wordMinusOneFromEnding <= 0) // make sure the value is more that 0,
continue // if more than zero, proced to next if statement
if(isThisAPalidrome(wordMinusOneFromEnding)){ // check if the word minus the first character, minus the last character = a plaindorme
if(wordMinusOneFromEnding.length > longestPalindromeLength){ // if it is
longestPalindromeLength = wordMinusOneFromEnding.length; // save its length
longestPalindrome = wordMinusOneFromEnding // and save the string itself
} // exit the statement that updates the longest palidrome
} // exit the stament that checks for a palidrome
} // exit the loop that goes backwards and takes a letter off the ending
} // exit the loop that goes forward and takes off the beginning letter
return console.log('heres the longest string: ' + longestPalindrome
+ ' its ' + longestPalindromeLength + ' charachters in length'); // return the longest palidrome! :)
}
findTheLongest('bananas');Это решение имеет O (n ^ 2) сложность. O (1) - сложность пространства.
public class longestPalindromeInAString {
public static void main(String[] args) {
String a = "xyMADAMpRACECARwl";
String res = "";
//String longest = a.substring(0,1);
//System.out.println("longest => " +longest);
for (int i = 0; i < a.length(); i++) {
String temp = helper(a,i,i);//even palindrome
if(temp.length() > res.length()) {res = temp ;}
temp = helper(a,i,i+1);// odd length palindrome
if(temp.length() > res.length()) { res = temp ;}
}//for
System.out.println(res);
System.out.println("length of " + res + " is " + res.length());
}
private static String helper(String a, int left, int right) {
while(left>= 0 && right <= a.length() -1 && a.charAt(left) == a.charAt(right)) {
left-- ;right++ ;
}
String curr = a.substring(left + 1 , right);
System.out.println("curr =>" +curr);
return curr ;
}
}
public static void main(String[] args) {
System.out.println(longestPalindromeString("9912333321456"));
}
static public String intermediatePalindrome(String s, int left, int right) {
if (left > right) return null;
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return s.substring(left + 1, right);
}
public static String longestPalindromeString(String s) {
if (s == null) return null;
String longest = s.substring(0, 1);
for (int i = 0; i < s.length() - 1; i++) {
//odd cases like 121
String palindrome = intermediatePalindrome(s, i, i);
if (palindrome.length() > longest.length()) {
longest = palindrome;
}
//even cases like 1221
palindrome = intermediatePalindrome(s, i, i + 1);
if (palindrome.length() > longest.length()) {
longest = palindrome;
}
}
return longest;
}
#longest palindrome
s='HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE'
out1=[]
def substring(x):
for i in range(len(x)):
a=x[i:]
b=x[:-i]
out1.append(a)
out1.append(b)
return out1
for i in range(len(s)):
substring(s[i:])
final=set([item for item in out1 if len(item)>2])
final
palind={item:len(item) for item in final if item==item[::-1]}
print(palind)
sorted(palind.items(),reverse=True, key=lambda x: x[1])[0]Вот мой алгоритм:
1) установите текущий центр как первую букву
2) одновременно расширяются влево и вправо, пока не найдете максимальный палиндром вокруг текущего центра.
3), если палиндром, который вы находите, больше, чем предыдущий палиндром, обновите его
4) установите текущий центр следующей буквой
5) повторите шаг 2) - 4) для всех букв в строке
Это выполняется в O (n).
Надеюсь, что это поможет.
Ссылка: Wikipedia.com
Лучший алгоритм, который я когда-либо нашел, со сложностью O (N)
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;
}
}
Мое решение:
static string GetPolyndrom(string str)
{
string Longest = "";
for (int i = 0; i < str.Length; i++)
{
if ((str.Length - 1 - i) < Longest.Length)
{
break;
}
for (int j = str.Length - 1; j > i; j--)
{
string str2 = str.Substring(i, j - i + 1);
if (str2.Length > Longest.Length)
{
if (str2 == str2.Reverse())
{
Longest = str2;
}
}
else
{
break;
}
}
}
return Longest;
}