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

Question

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

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

Алго 1:

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

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

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

Алго 2:

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

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

Answer 1

Вы можете найти самый длинный палиндром, используя Алгоритм Манахера за O(n) время! Его реализацию можно найти здесь и здесь .

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

Answer 2

Алго 2 может не работать для всей строки. Вот пример такой строки "ABCDEFCBA".

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

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

Answer 3

Насколько я понял проблему, мы можем найти палиндромы вокруг индекса центра и охватить наш поиск в обоих направлениях, вправо и влево от центра. Учитывая это и зная, что по углам ввода нет палиндрома, мы можем установить границы на 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

Answer 4

с помощью регулярных выражений и рубинов вы можете сканировать короткие палиндромы следующим образом:

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 5

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

Эффективное 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) * * 1016 (.) (.) (.) (\ 3) (\ 2) (\ 1)

VBS

Dim strTest
wscript.echo Palindrome("abaccddccefe")

* 1026 УВА *

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 7

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

Из любопытства я написал следующую программу на 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);
    }
}

Answer 9

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

import java.util.Arrays; открытый класс ManachersAlgorithm { public static String findLongestPalindrome (String s) { if (s == null || s.length () == 0) возврат "";

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 10

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