Напишите функцию, которая возвращает самый длинный палиндром в данной строке

например, "ccddcc" в строке "abaccddccefe"

Я думал о решении, но оно работает за O (n ^ 2) времени

Алго 1:

Шаги: это метод грубой силы

Есть 2 для петель
для i = от 1 до i меньше, чем array.length -1
for j = i + 1 до j меньше, чем array.length Таким образом, вы можете получить подстроку каждой возможной комбинации из массива Имеет функцию палиндрома, которая проверяет, является ли строка палиндромомso для каждой подстроки (i, j) вызовите эту функцию, если это палиндром, сохраните ее в строковой переменной Если вы найдете следующую подстроку палиндрома и если она больше текущей, замените ее текущей. Наконец, ваша строковая переменная будет иметь ответ

Вопросы: 1. Этот алгоритм работает за O (n ^ 2) времени.

Алго 2:

Пересмотрите строку и сохраните ее в другом массиве Теперь найдите самую подходящую подстроку между двумя массивами Но это тоже работает за O (n ^ 2) время

Можете ли вы, ребята, подумать о алгоритме, который работает в лучшее время. Если возможно O (n) время

 viki.omega922 мар. 2013 г., 18:03
Что если бы я знал, что работаю с палиндромом и сохраняю свои строки как две половины, а затем, если бы я использовал Java, я бы проверил O (1) на функцию?
 Yarneo13 июл. 2013 г., 12:16
Алгоритм секонга правильный? Как насчет строки: "abcdecba". Самая большая подходящая подстрока (abcdecba или abcedcba): abc или cba. Однако оба не являются палиндромами.
 Zolt15 нояб. 2013 г., 03:29
@ Learner, просто любопытно, в каких шагах вы выше, на какой массив ссылаетесь в своих циклах for? По массиву вы ссылаетесь на строку? String.length?
 Skylar Saveland03 окт. 2012 г., 22:48
Думаю, первоеO(n^2) чтобы получить подстроки *O(n) чтобы проверить, являются ли они палиндромами, в общей сложностиO(n^3)?
 Shirish Herwade17 мая 2018 г., 10:15

Ответы на вопрос(21)

Алгоритм Манахера вO(n) время! Его реализацию можно найтиВо а такжеВо.

Для вводаString s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" находит правильный вывод1234567887654321.

 v.oddou11 июл. 2016 г., 11:52
Я не понимаю, как это линейно. я вижуwhile встроен вfor с ограничением, похожим на внешний цикл.

EFCBA".

Не то, чтобы строка имела «ABC» и «CBA» в качестве подстроки. Если вы перевернете исходную строку, это будет «ABCFEDCBA». и самая длинная подходящая подстрока - "ABC", которая не является палиндромом.

Вам может потребоваться дополнительно проверить, является ли эта самая длинная совпадающая подстрока действительно палиндромом, у которого время работы O (n ^ 3).

 Jake Drew06 дек. 2013 г., 08:10
Важно отметить, что алгоритм Algo 2 должен работать для «самого длинного совпадающего палиндрома подпоследовательности», что является распространенной проблемой алгоритмов, когда символы подпоследовательности также могут быть разделены внутри строки. Например, самая длинная совпадающая подпоследовательность (включая символьное разделение) между двумя приведенными выше строками - это «ABCFCBA», которая также является палиндромом :) Вот ссылка, описывающая проблему LCS: Ics.uci.edu / ~ Эпштайна / 161 / 960229.html

вы можете отсканировать короткие палиндромы, как это:

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;
}

Это определенно можно было бы немного улучшить и оптимизировать, но оно должно иметь довольно хорошую производительность во всех случаях, кроме сценария наихудшего случая (строка с той же буквой).

 v.oddou14 июл. 2016 г., 08:47
ты называешь это "простым", но оно полноi j l s if и государственное обслуживание. множественные точки возврата, крайние случаи ...
 j_random_hacker16 сент. 2012 г., 09:53
Я изначально думал, что алгоритм # 1 ОП был O (n ^ 2) времени, но на самом деле это тупо O (n ^ 3), так что даже если ваш алгоритм не доходит до достижимой границы O (n) , это все еще улучшение.
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;
    }

1) установить текущий центр на первую букву

2) одновременно расширяйтесь влево и вправо, пока не найдете максимальный палиндром вокруг текущего центра

3) если найденный вами палиндром больше предыдущего, обновите его

4) установить текущий центр на следующую букву

5) повторите шаги с 2) по 4) для всех букв в строке

Это работает в O (n).

Надеюсь, это поможет

 paislee13 июн. 2012 г., 21:12
Рассмотрите строку "aaaaaa". Это выполняется в O (n ^ 2) с использованием вашего алгоритма.
 j_random_hacker16 сент. 2012 г., 09:54
Я изначально думал, что алгоритм # 1 ОП был O (n ^ 2) времени, но на самом деле это тупо O (n ^ 3), так что даже если ваш алгоритм не доходит до достижимой границы O (n) , это все еще улучшение.
 v.oddou14 июл. 2016 г., 08:53
Это классическое решение для расширения N2. НО, на самом деле это близко к решению Manacher, как объяснено в этом видео: Youtube.com / смотреть? V = V-sEwsca1ak разница в пункте 4. Менеджер повторно использует информацию, чтобы избежать повторного сканирования уже отсканированных букв.

вует еще один алгоритм, называемый Gusfield's 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) или алгоритм Манахера из мой собственный блог.

мы можем найти палиндромы вокруг центрального указателя и охватить наш поиск в обоих направлениях - вправо и влево от центра. Учитывая это и зная, что по углам ввода нет палиндрома, мы можем установить границы на 1 и длину-1. Обращая внимание на минимальные и максимальные границы строки, мы проверяем, одинаковы ли символы в позициях симметричных индексов (справа и слева) для каждой центральной позиции, пока мы не достигнем нашего максимального верхнего ограничительного центра.

Внешний цикл равен O (n) (максимум n-2 итерации), а внутренний цикл while равен O (n) (максимум вокруг (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
 Elbek04 июн. 2012 г., 05:08
Если я даю "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" Это не работает, но ответ должен быть 1234567887654321
 j_random_hacker14 июл. 2016 г., 12:39
@ v.oddou: Вы абсолютно правы, и я не знаю, как я пришел к выводу O (n ^ 3), учитывая, что есть только 2 вложенных цикла! Я удалю этот ошибочный комментарий ... Но я также заметил, что у этого решения есть проблема, которую я добавлю в отдельный комментарий, чтобы автор, надеюсь, заметил.
 j_random_hacker14 июл. 2016 г., 12:42
Мои предыдущие заявления о сложности времени O (n ^ 3) были неправильными (спасибо @ v.oddou за то, что указал на это!), Но есть еще одна проблема: этот код не учитывает палиндромы четной длины. Это можно исправить, добавив второй, очень похожий внешний цикл (также O (n ^ 2), чтобы он не влиял на сложность времени O (n ^ 2)), который расширяет палиндромы вокруг каждой из n-1 позициймежд каждая пара символов. +2 если исправишь
 v.oddou14 июл. 2016 г., 08:45
@ j_random_hacker Нет, это одно из квадратичных решений. Это покрытоВо какexpandAroundCenter.

чтобы найти самый длинный палиндром в строке. Пожалуйста, обратитесь к следующей ссылке, чтобы понять алгоритмhttp: //stevekrenzel.com/articles/longest-palnidrom

Используются данные тестирования: 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;     
  }
 st0le09 мар. 2011 г., 06:38
никогда не читал свой предыдущий комментарий до сегодняшнего дня ... вы не обращались ко мне в прошлый раз .... не торопитесь, это было просто наблюдение.
 j_random_hacker16 сент. 2012 г., 09:56
Я изначально думал, что алгоритм # 1 ОП был O (n ^ 2) времени, но на самом деле это тупо O (n ^ 3), так что даже если ваш алгоритм не доходит до достижимой границы O (n) , это все еще улучшение.
 Mohit Bhandari26 февр. 2011 г., 21:12
Это работает даже для палиндромов. Вы можете запустить эту программу и сообщить мне, если она не работает. Для понимания алгоритма, пожалуйста, обратитесь к следующей ссылке Stevekrenzel.com / статьи / длинный-palnidrome
 Mohit Bhandari08 мар. 2011 г., 13:52
@ st0le: Эта логика не будет работать даже для палиндромов, но она может быть скорректирована даже для палиндромов. Просим прощения за предыдущий компонент. Я получил логику и обновлю ее через несколько дней, как и когда у меня будет время.
 st0le19 февр. 2011 г., 10:11
Я не уверен, что это работает с палиндромами одинаковой длины ... можешь подтвердить?

Статья в Википедии по этой теме. Образец Алгоритм Манахера Java реализация линейного O (n) решения из статьи ниже:

import java.util.Arrays; открытый класс ManachersAlgorithm {открытая статическая строка 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;   }     }

Regexp решение, которое избегает грубой силы

Начинается со всей длины строки и работает вниз до 2 символов, существует, как только найдено совпадение

Для"abaccddccefe" регулярное выражение проверяет 7 совпадений перед возвратомccddcc.

(.) (.) (.) (.) (.) (.) (\ 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)

VBS

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
 brettdj04 февр. 2016 г., 09:45
@ DickKusleika Можете ли вы обновить мой комментарий на Dailydoseofexcel.com / Архивы / 2016/01/14 / ... с исправленным кодом выше. Спасиб

простую и понятную 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);
    }
}

TYGDE"; Это должно работать для четных и нечетных приятелей. Большое спасибо Мохиту!

using пространства имен 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;
}
 j_random_hacker16 сент. 2012 г., 09:50
Этопочт делает вещи за O (n ^ 2) раз. Зачем строитьisPal - операция O (n) - только для измерения ее длины !? Также у него есть ошибка при обработке даже палиндромов. На четно-палиндромной волнистости:else if(input_str[i] == input_str[j]) никогда не может быть успешным, потому что этот же тест не прошел в предыдущемif заявление; и в любом случае это глючит, потому что вы не можете сказать, просто глядя на 2 символа, разделенных на 2 позиции, смотрите ли вы на четный или нечетный палиндром (рассмотримAAA а такжеAAAA).

Не лучшее решение, но работает в обоих случаях

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 # c # d # c # b # c

palinCount = 1010105010301

длина самого длинного палиндрома = 5;

longest палиндром = bcdcb

public class 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;

    }

}

}

Это вернет самую длинную строку палиндрома из данной строки

-(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"];
}

== ВЫХОД ===

Input: abcccde Вывод: ccc

Input: abcccbd Вывод: bcccb

Input: abedccde Вывод: edccde

Input: abcccdeed Вывод: deed

Input: abcccbadeed Вывод: abcccba

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');

 alex bennett17 июн. 2016 г., 01:22
Не знаю, почему за это проголосовали - работает как шарм. Получил меня через интервью с технологиями CA просто отлично.

Это решение 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 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"));
}

}
 Vivek Mishra24 июн. 2017 г., 09:26
это дает всем палиндрому в строке не только самый длинный

мое решение:

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;
}
 j_random_hacker16 сент. 2012 г., 09:56
Это займет Кубический время в длине строки, из-заSubstring() и равенство строк ==) операции. Он в основном идентичен алгоритму ОП № 1.

Лучший алгоритм, который я когда-либо нашел, со сложностью O (N)

 
 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;
  }    
}
 aladine20 мая 2014 г., 15:56
Это из Википедии

Ваш ответ на вопрос