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

Question

например «ccddcc» в строке «abaccddccefe»

Я думал о решении, но он работает в O времени

(п^2)

Algo 1:

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

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

вопросы: 1. Этот алго запускается в O (N^2) время.

Algo 2:

1. Reverse строки и сохранить ее в Diferent массива
2. Теперь найти самую большую найденную подстроку между оба массивом
3. Но это тоже работает в O (N^2) время

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

Answer 1

Мне недавно задали этот вопрос. Вот решение, которое я [в конечном итоге] придумал. Я сделал это в 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; 
} 

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

Answer 2

Algo 2 может не работать для всех строк. Вот пример такой строки «ABCDEFCBA».

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

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

Answer 3

Hi Вот мой код, чтобы найти самый длинный палиндром в строке. Пожалуйста, обратитесь к следующей ссылке, чтобы понять алгоритм 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;  
    } 

Answer 4

Попробуйте строку - «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; 
} 

Answer 5

мое решение:

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

Answer 6

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

Внешний контур представляет собой О (п) (макс N-2 итерации), а внутренний в то время как цикл О (п) (макс вокруг (п/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 

Answer 7

Вот мой алгоритм:

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

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

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

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

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

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

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

Answer 8

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

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 

Answer 9

После кода вычисляет 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; 
} 

Answer 10

Вы можете найти самую длинную палиндром, используя Manacher's Algorithm в O(n) время! Его реализация может быть найдена here и here.

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

Answer 11

Эффективного 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") 

vba

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 

Answer 12

1. Изменить строку для разделения каждого символа, используя разделитель [этого является включение нечетных и четных палиндромы]
2. Найти палиндромы вокруг каждого символа как центр

Мы можем найти все палиндромы всей длины, используя это.

Пример:

слово = abcdcbc

modifiedString = A # B # C# D # C# 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; 

    } 

} 

}

Answer 13

Здесь я написал логику попробовать :)

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

} 

Answer 14

Лучший алгоритм я когда-либо находились со сложностью 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; 
    }  
} 

Answer 15

См. Wikipedia article по этой теме. Пример Manacher's Algorithm Реализация Java для линейного решения 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; }  } 

Answer 16

Для линейного решения, вы можете использовать алгоритм Manacher в. Существует другой алгоритм вызов Gusfield в алгоритме, и ниже код в 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 от my own blog.

Answer 17

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

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

== ВЫВОД ===

Вход: abcccde Выход: ссс

Вход: abcccbd Выход: bcccb

Вход: abedccde Выход: edccde

Вход: abcccdeed Out говоря: дело

Вход: abcccbadeed Выход: abcccba

Answer 18

Вот реализация в 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');

Answer 19

Я написал следующую программу 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); 
    } 
}