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

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

#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]

{'DED': 3, '123456789987654321': 18, '67899876': 8, 'ABCDEDCBA': 9, '456789987654': 12, '34567899876543': 14, 'BCDEDCB': 7, 'ABA': 3, «5678998765»: 10, «2345678998765432»: 16, «CDEDC»: 5, «789987»: 6, «8998»: 4} ('123456789987654321', 18)

Answer 2

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

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

Образец:

word = abcdcbc

ifiedString = 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;

    }

}

}