Рубрики

Длинная палиндромная подстрока | Набор 2

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

Мы обсудили динамическое программирование решения в предыдущем посте . Временная сложность решения на основе динамического программирования составляет O (n ^ 2) и требует O (n ^ 2) дополнительного пространства. Мы можем найти самую длинную подстроку палиндрома за (n ^ 2) времени с O (1) дополнительным пробелом. Идея состоит в том, чтобы генерировать все палиндромы четной и нечетной длины и отслеживать самый длинный палиндром, который когда-либо наблюдался.

Шаг для генерации нечетной длины палиндрома:
Зафиксируйте центр и расширьте в обоих направлениях для более длинных палиндромов.

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

C ++

// AO (n ^ 2) время и O (1) космическая программа для
// найти самую длинную палиндромную подстроку
#include <bits/stdc++.h>

using namespace std;

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

void printSubStr(char* str, int low, int high) 

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

        cout << str[i]; 

  
// Эта функция печатает самую длинную подстроку палиндрома (LPS)
// из str []. Он также возвращает длину самого длинного палиндрома

int longestPalSubstr(char *str) 

    int maxLength = 1; // Результат (длина LPS)

  

    int start = 0; 

    int len = strlen(str); 

  

    int low, high; 

  

    // Один за другим рассматриваем каждый символ как центральную точку

    // четные и длинные палиндромы

    for (int i = 1; i < len; ++i) 

    

        // Находим самый длинный четный палиндром

        // с центральными точками как i-1 и i.

        low = i - 1; 

        high = i; 

        while (low >= 0 && high < len && str[low] == str[high]) 

        

            if (high - low + 1 > maxLength) 

            

                start = low; 

                maxLength = high - low + 1; 

            

            --low; 

            ++high; 

        

  

        // Находим самый длинный нечетной длины палиндром с центром

        // указать как я

        low = i - 1; 

        high = i + 1; 

        while (low >= 0 && high < len && str[low] == str[high]) 

        

            if (high - low + 1 > maxLength) 

            

                start = low; 

                maxLength = high - low + 1; 

            

            --low; 

            ++high; 

        

    

  

    cout<<"Longest palindrome substring is: "

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

  

    return maxLength; 

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

int main() 

    char str[] = "forgeeksskeegfor"

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

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// AO (n ^ 2) время и O (1) космическая программа, чтобы найти самую длинную палиндромную подстроку
#include <stdio.h>
#include <string.h>

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

void printSubStr(char* str, int low, int high)

{

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

        printf("%c", str[i]);

}

  
// Эта функция печатает самую длинную подстроку палиндрома (LPS)
// из str []. Он также возвращает длину самого длинного палиндрома

int longestPalSubstr(char *str)

{

    int maxLength = 1;  // Результат (длина LPS)

  

    int start = 0;

    int len = strlen(str);

  

    int low, high;

  

    // Один за другим рассматриваем каждый символ как центральную точку

    // четные и длинные палиндромы

    for (int i = 1; i < len; ++i)

    {

        // Находим самый длинный палиндром четной длины с центральными точками

        // как я-1 и я.

        low = i - 1;

        high = i;

        while (low >= 0 && high < len && str[low] == str[high])

        {

            if (high - low + 1 > maxLength)

            {

                start = low;

                maxLength = high - low + 1;

            }

            --low;

            ++high;

        }

  

        // Находим самый длинный нечетной длины палиндром с центром

        // указать как я

        low = i - 1;

        high = i + 1;

        while (low >= 0 && high < len && str[low] == str[high])

        {

            if (high - low + 1 > maxLength)

            {

                start = low;

                maxLength = high - low + 1;

            }

            --low;

            ++high;

        }

    }

  

    printf("Longest palindrome substring is: ");

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

  

    return maxLength;

}

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

int main()

{

    char str[] = "forgeeksskeegfor";

    printf("\nLength is: %d", longestPalSubstr( str ) );

    return 0;

}

Джава

// Java-реализация метода времени O (n ^ 2) и пространства O (1)
// найти самую длинную палиндромную подстроку

public class LongestPalinSubstring

{

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

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

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

    }

  

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

    // (LPS) str []. Он также возвращает длину

    // самый длинный палиндром

    static int longestPalSubstr(String str) {

        int maxLength = 1; // Результат (длина LPS)

  

        int start = 0;

        int len = str.length();

  

        int low, high;

  

        // один за другим считаем каждый символ центром

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

        for (int i = 1; i < len; ++i) 

        {

            // Находим самый длинный палиндром четной длины с

            // центральные точки как i-1 и i.

            low = i - 1;

            high = i;

            while (low >= 0 && high < len

                    && str.charAt(low) == str.charAt(high)) {

                if (high - low + 1 > maxLength) {

                    start = low;

                    maxLength = high - low + 1;

                }

                --low;

                ++high;

            }

  

            // Находим самый длинный нечетной длины палиндром с

            // центральная точка как я

            low = i - 1;

            high = i + 1;

            while (low >= 0 && high < len

                    && str.charAt(low) == str.charAt(high)) {

                if (high - low + 1 > maxLength) {

                    start = low;

                    maxLength = high - low + 1;

                }

                --low;

                ++high;

            }

        }

  

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

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

  

        return maxLength;

    }

  

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

    public static void main(String[] args) {

          

        String str = "forgeeksskeegfor";

        System.out.println("Length is: "

                           longestPalSubstr(str));

    }

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

питон

# AO (n ^ 2) время и O (1) космическая программа, чтобы найти
#longest палиндромная подстрока

  
# Эта функция печатает самую длинную палиндромную подстроку (LPS)
№ стр []. Он также возвращает длину самого длинного палиндрома

def longestPalSubstr(string):

    maxLength = 1

  

    start = 0

    length = len(string)

  

    low = 0

    high = 0

  

    # Один за другим рассматривайте каждого персонажа как центральную точку

    # четность и длина палиндромов

    for i in xrange(1, length):

        # Найти самый длинный четный палиндром с центром

    # очков как я-1 и я.

        low = i - 1

        high = i

        while low >= 0 and high < length and string[low] == string[high]:

            if high - low + 1 > maxLength:

                start = low

                maxLength = high - low + 1

            low -= 1

            high += 1

  

        # Найти самую длинную нечетную длину палиндрома с центром

        # указать как я

        low = i - 1

        high = i + 1

        while low >= 0 and high < length and string[low] == string[high]:

            if high - low + 1 > maxLength:

                start = low

                maxLength = high - low + 1

            low -= 1

            high += 1

  

    print "Longest palindrome substring is:",

    print string[start:start + maxLength]

  

    return maxLength

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

string = "forgeeksskeegfor"

print "Length is: " + str(longestPalSubstr(string))

  
# Этот код предоставлен BHAVYA JAIN

C #

// C # реализация времени O (n ^ 2)
// и O (1) космический метод, чтобы найти
// самая длинная палиндромная подстрока

using System;

  

class GFG

{
// Утилита для печати
// подстрока str [low..high]

public static void printSubStr(string str,  

                               int low, int high)

{

    Console.WriteLine(str.Substring(low, 

                     (high + 1) - low));

}

  
// Эта функция печатает самый длинный
// палиндромная подстрока (LPS) str [].
// Он также возвращает длину
// самый длинный палиндром

public static int longestPalSubstr(string str)

{

    int maxLength = 1; // Результат (длина LPS)

  

    int start = 0;

    int len = str.Length;

  

    int low, high;

  

    // Рассмотрим каждый

    // символ в качестве центральной точки

    // четных и длинных палиндромов

    for (int i = 1; i < len; ++i)

    {

        // Находим самую длинную четную длину

        // палиндром с центральными точками

        // как я-1 и я.

        low = i - 1;

        high = i;

        while (low >= 0 && high < len && 

               str[low] == str[high])

        {

            if (high - low + 1 > maxLength)

            {

                start = low;

                maxLength = high - low + 1;

            }

            --low;

            ++high;

        }

  

        // Находим самую длинную нечетную длину

        // палиндром с центральной точкой как я

        low = i - 1;

        high = i + 1;

        while (low >= 0 && high < len && 

               str[low] == str[high])

        {

            if (high - low + 1 > maxLength)

            {

                start = low;

                maxLength = high - low + 1;

            }

            --low;

            ++high;

        }

    }

  

    Console.Write("Longest palindrome substring is: ");

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

  

    return maxLength;

}

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

public static void Main(string[] args)

{

    string str = "forgeeksskeegfor";

    Console.WriteLine("Length is: " +

                       longestPalSubstr(str));

}
}

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

PHP

<?php 
// AO (n ^ 2) время и O (1) космическая программа, чтобы найти самую длинную палиндромную подстроку

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

function printSubStr($str, $low, $high)

{

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

        echo $str[$i];

}

   
// Эта функция печатает самую длинную подстроку палиндрома (LPS)
// из str []. Он также возвращает длину самого длинного палиндрома

function longestPalSubstr($str)

{

    $maxLength = 1;  // Результат (длина LPS)

   

    $start = 0;

    $len = strlen($str);

   

    // Один за другим рассматриваем каждый символ как центральную точку

    // четные и длинные палиндромы

    for ($i = 1; $i < $len; ++$i)

    {

        // Находим самый длинный палиндром четной длины с центральными точками

        // как я-1 и я.

        $low = $i - 1;

        $high = $i;

        while ($low >= 0 && $high < $len && $str[$low] == $str[$high])

        {

            if ($high - $low + 1 > $maxLength)

            {

                $start = $low;

                $maxLength = $high - $low + 1;

            }

            --$low;

            ++$high;

        }

   

        // Находим самый длинный нечетной длины палиндром с центром

        // указать как я

        $low = $i - 1;

        $high = $i + 1;

        while ($low >= 0 && $high < $len && $str[$low] == $str[$high])

        {

            if ($high - $low + 1 > $maxLength)

            {

                $start = $low;

                $maxLength = $high - $low + 1;

            }

            --$low;

            ++$high;

        }

    }

   

    echo "Longest palindrome substring is: ";

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

   

    return $maxLength;

}

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

  

$str = "forgeeksskeegfor";

echo "\nLength is: ". longestPalSubstr( $str ) ;

return 0;

?>

Выход:

Longest palindrome substring is: geeksskeeg
Length is: 10

Сложность по времени: O (n ^ 2) где n — длина входной строки.
Вспомогательное пространство: O (1)

Вскоре мы добавим более оптимизированный метод в виде отдельного поста.

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

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

Длинная палиндромная подстрока | Набор 2

0.00 (0%) 0 votes