Рубрики

Длинная палиндромная подстрока | Комплект 1

По заданной строке найдите самую длинную подстроку — палиндром. Например, если заданная строка «forgeeksskeegfor», вывод должен быть «geeksskeeg».

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

Временная сложность : O (n ^ 3)
Вспомогательная сложность : O (1)

Метод 2 (динамическое программирование)
Сложность времени может быть уменьшена путем сохранения результатов подзадач. Идея похожа на этот пост. Мы поддерживаем булеву таблицу [n] [n], которая заполняется снизу вверх. Значение таблицы [i] [j] равно true, если подстрока — палиндром, в противном случае — false. Чтобы вычислить таблицу [i] [j], мы сначала проверяем значение таблицы [i + 1] [j-1], если значение равно true и str [i] совпадает с str [j], то мы создаем таблицу [я] [j] правда. В противном случае значение таблицы [i] [j] становится ложным.

Ниже приведена реализация вышеуказанного подхода:

C / C ++

// C ++ динамическое программирование
// решение для самого длинного палиндрома

  
#include <bits/stdc++.h>

using namespace std; 

  

  
// Функция для печати подстроки str [low..high]

void printSubStr( string str, int low, int high )

{

    for( int i = low; i <= high; ++i )

        cout << str[i];

}

  
// Эта функция печатает самую длинную подстроку палиндрома
// Он также возвращает длину самого длинного палиндрома

int longestPalSubstr(string str)

{

    // получаем длину входной строки

    int n = str.size(); 

  

    // таблица [i] [j] будет ложной, если подстрока str [i..j]

    // не является палиндромом.

    // Иначе таблица [i] [j] будет истинной

    bool table[n][n];

      

    memset(table, 0, sizeof(table));

  

    // Все подстроки длины 1 являются палиндромами

    int maxLength = 1;

      

    for (int i = 0; i < n; ++i)

        table[i][i] = true;

  

    // проверка подстроки длины 2.

    int start = 0;

    for (int i = 0; i < n-1; ++i)

    {

        if (str[i] == str[i+1])

        {

            table[i][i+1] = true;

            start = i;

            maxLength = 2;

        }

    }

  

    // Проверка длины больше 2. k - это длина

    // подстроки

    for (int k = 3; k <= n; ++k)

    {

        // Исправить начальный индекс

        for (int i = 0; i < n-k+1 ; ++i)

        {

            // Получить конечный индекс подстроки из

            // начальный индекс i и длина k

            int j = i + k - 1;

  

            // проверка подстроки из i-го индекса в

            // j-й индекс, если str [i + 1] to str [j-1] является

            // палиндром

            if (table[i+1][j-1] && str[i] == str[j])

            {

                table[i][j] = true;

  

                if (k > maxLength)

                {

                    start = i;

                    maxLength = k;

                }

            }

        }

    }

  

   cout << "Longest palindrome substring is: ";

   printSubStr( str, start, start + maxLength - 1 );

      

    // возвращаем длину LPS

    return maxLength;

}

  
// Код драйвера

int main()

{

    string str = "forgeeksskeegfor";

    cout << "\nLength is: " << longestPalSubstr( str );

    return 0;

}

Джава

// Решение Java

public class LongestPalinSubstring 

{

    // Вспомогательная функция для печати подстроки str [low..high]

    static void printSubStr(String str, int low, int high) {

        System.out.println(str.substring(low, high + 1));

    }

  

    // Эта функция печатает самую длинную подстроку палиндрома

    // из str [].

    // Он также возвращает длину самого длинного палиндрома

    static int longestPalSubstr(String str) {

        int n = str.length();   // получаем длину входной строки

  

        // таблица [i] [j] будет ложной, если подстрока str [i..j]

        // не является палиндромом.

        // Иначе таблица [i] [j] будет истинной

        boolean table[][] = new boolean[n][n];

  

        // Все подстроки длины 1 являются палиндромами

        int maxLength = 1;

        for (int i = 0; i < n; ++i)

            table[i][i] = true;

  

        // проверка подстроки длины 2.

        int start = 0;

        for (int i = 0; i < n - 1; ++i) {

            if (str.charAt(i) == str.charAt(i + 1)) {

                table[i][i + 1] = true;

                start = i;

                maxLength = 2;

            }

        }

          

        // Проверка длины больше 2. k - это длина

        // подстроки

        for (int k = 3; k <= n; ++k) {

              

                  // Исправить начальный индекс

            for (int i = 0; i < n - k + 1; ++i) 

            {

                // Получить конечный индекс подстроки из

                // начальный индекс i и длина k

                int j = i + k - 1;

  

                // проверка подстроки из i-го индекса в

                // j-й индекс, если str.charAt (i + 1) для

                // str.charAt (j-1) - палиндром

                if (table[i + 1][j - 1] && str.charAt(i) == 

                                          str.charAt(j)) {

                    table[i][j] = true;

  

                    if (k > maxLength) {

                        start = i;

                        maxLength = k;

                    }

                }

            }

        }

        System.out.print("Longest palindrome substring is; ");

        printSubStr(str, start, start + maxLength - 1);

          

        return maxLength; // возвращаем длину LPS

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) {

  

        String str = "forgeeksskeegfor";

        System.out.println("Length is: "

                                 longestPalSubstr(str));

    }

}

  
// Этот код предоставлен Sumit Ghosh

питон

# Python программа

  

import sys

  
# Полезная функция для печати
# подстрока str [low..high]

def printSubStr(st,low,high) :

    sys.stdout.write(st[low : high + 1])

    sys.stdout.flush()

    return ''

  
# Эта функция печатает самый длинный палиндром
# подстрока st []. Это также возвращает длину
# самого длинного палиндрома

def longestPalSubstr(st) :

    n = len(st) # получить длину входной строки

  

    # table [i] [j] будет false если подстрока

    # str [i..j] не является палиндромом. еще

    # table [i] [j] будет истинным

    table = [[0 for x in range(n)] for y

                          in range(n)] 

      

    # Все подстроки длины 1

    # палиндромы

    maxLength = 1

    i = 0

    while (i < n) :

        table[i][i] = True

        i = i + 1

      

    # проверить подстроку длины 2.

    start = 0

    i = 0

    while i < n - 1 :

        if (st[i] == st[i + 1]) :

            table[i][i + 1] = True

            start = i

            maxLength = 2

        i = i + 1

      

    # Проверьте длину больше 2.

    # k - длина подстроки

    k = 3

    while k <= n :

        # Исправить начальный индекс

        i = 0

        while i < (n - k + 1) :

              

            # Получить конечный индекс

            # подстрока от начала

            # индекс i и длина k

            j = i + k - 1

      

            # проверка подстроки из

            # с индекса на индекс j

            # st [i + 1] to st [(j-1)] является

            # палиндром

            if (table[i + 1][j - 1] and 

                      st[i] == st[j]) :

                table[i][j] = True

      

                if (k > maxLength) :

                    start = i

                    maxLength = k

            i = i + 1

        k = k + 1

    print "Longest palindrome substring is: ",printSubStr(st, start,

                                               start + maxLength - 1)

  

    return maxLength # возвращаемая длина LPS

  

  
# Драйверная программа для проверки вышеуказанных функций

st = "forgeeksskeegfor"

l = longestPalSubstr(st)

print "Length is:", l

  
# Этот код предоставлен Никитой Тивари.


Выход :

Longest palindrome substring is: geeksskeeg
Length is: 10

Сложность времени : O (n ^ 2)
Вспомогательное пространство : O (n ^ 2)

Лучший подход к сложности космоса можно найти в наборе 2 .

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Длинная палиндромная подстрока | Комплект 1

0.00 (0%) 0 votes