Рубрики

Найти все различные палиндромные подстроки данной строки

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

Примеры:

Input: str = "abaaa"
Output:  Below are 5 palindrome sub-strings
a
aa
aaa
aba
b


Input: str = "geek"
Output:  Below are 4 palindrome sub-strings
e
ee
g
k

Шаг 1: Поиск всех палиндромов с использованием модифицированного алгоритма Манахера:
Рассматривая каждый символ как сводный, разверните с обеих сторон, чтобы найти длину как палиндромов четной, так и нечетной длины с центром в рассматриваемом поворотном символе, и сохраните длину в 2 массивах (нечетные и четные).
Временная сложность для этого шага O (n ^ 2)

Шаг 2: Вставка всех найденных палиндромов в HashMap:
Вставьте все палиндромы, найденные в предыдущем шаге, в HashMap. Также вставьте все отдельные символы из строки в HashMap (для генерации отдельных однобуквенных палиндромных подстрок).
Временная сложность этого шага составляет O (n ^ 3), если предположить, что поиск вставки в хэш занимает O (1) время. Обратите внимание, что в строке может быть не более O (n ^ 2) палиндромных подстрок. В приведенном ниже коде C ++ используется упорядоченная хэш-карта, где временная сложность вставки и поиска равна O (Logn). В C ++ упорядоченный hashmap реализован с использованием Red Black Tree .

Шаг 3: Печать отдельных палиндромов и количество таких различных палиндромов:
Последний шаг — распечатать все значения, хранящиеся в HashMap (из-за свойства HashMap будут хэшироваться только отдельные элементы). Размер карты дает количество различных палиндромных непрерывных подстрок.

Ниже приведена реализация вышеуказанной идеи.

C / C ++

// C ++ программа для поиска всех различных подстрок палиндрома
// данной строки
#include <iostream>
#include <map>

using namespace std;

  
// Функция для печати всех различных палиндромных подстрок s

void palindromeSubStrs(string s)

{

    map<string, int> m;

    int n = s.size();

  

    // таблица для хранения результатов (2 строки для нечетных

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

    int R[2][n+1];

  

    // Найти все подстроки палиндромов из заданного ввода

    // строка вставляет 'охранники' для легкой итерации

    s = "@" + s + "#";

  

    for (int j = 0; j <= 1; j++)

    {

        int rp = 0;   // длина радиуса палиндрома

        R[j][0] = 0;

  

        int i = 1;

        while (i <= n)

        {

            // Попытка расширить палиндром с центром в i

            while (s[i - rp - 1] == s[i + j + rp])

                rp++;  // Увеличиваем длину палиндромного

                       // радиус, как и когда мы находим Vaid Palindrome

  

            // Назначаем найденную палиндромную длину нечетным / четным

            // массив длины

            R[j][i] = rp;

            int k = 1;

            while ((R[j][i - k] != rp - k) && (k < rp))

            {

                R[j][i + k] = min(R[j][i - k],rp - k);

                k++;

            }

            rp = max(rp - k,0);

            i += k;

        }

    }

  

    // убираем «охранников»

    s = s.substr(1, n);

  

    // Поместить все полученные палиндромы в хэш-карту в

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

    m[string(1, s[0])]=1;

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

    {

        for (int j = 0; j <= 1; j++)

            for (int rp = R[j][i]; rp > 0; rp--)

               m[s.substr(i - rp - 1, 2 * rp + j)]=1;

        m[string(1, s[i])]=1;

    }

  

    // печать всех отдельных палиндромов из хэш-карты

   cout << "Below are " << m.size()-1

        << " palindrome sub-strings";

   map<string, int>::iterator ii;

   for (ii = m.begin(); ii!=m.end(); ++ii)

      cout << (*ii).first << endl;

}

  
// Драйвер программы

int main()

{

    palindromeSubStrs("abaaa");

    return 0;

}

Джава

// Java-программа для поиска всех различных палиндромов
// подстроки данной строки

import java.util.Map;

import java.util.TreeMap;

  

public class GFG 

{     

    // Функция для печати всех различных палиндромов

    // подстроки s

    static void palindromeSubStrs(String s)

    {

        // map <string, int> m;

        TreeMap<String , Integer> m = new TreeMap<>();

        int n = s.length();

       

        // таблица для хранения результатов (2 строки для нечетных

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

        int[][] R = new int[2][n+1];

       

        // Найти все подстроки палиндромов из

        // заданную входную строку вставляем 'guards' в

        // легко повторяем по s

        s = "@" + s + "#";

       

        for (int j = 0; j <= 1; j++)

        {

            int rp = 0;   // длина радиуса палиндрома

            R[j][0] = 0;

       

            int i = 1;

            while (i <= n)

            {

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

                // у меня

                while (s.charAt(i - rp - 1) == s.charAt(i + 

                                                j + rp))

                    rp++;  // Увеличиваем длину

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

                           // когда мы находим Vaid Palindrome

       

                // Назначаем найденную палиндромную длину

                // в нечетную / четную длину массива

                R[j][i] = rp;

                int k = 1;

                while ((R[j][i - k] != rp - k) && (k < rp))

                {

                    R[j][i + k] = Math.min(R[j][i - k], 

                                              rp - k);

                    k++;

                }

                rp = Math.max(rp - k,0);

                i += k;

            }

        }

       

        // убираем «охранников»

        s = s.substring(1, s.length()-1);

       

        // Поместить все полученные палиндромы в хэш-карту в

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

        m.put(s.substring(0,1), 1);

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

        {

            for (int j = 0; j <= 1; j++)

                for (int rp = R[j][i]; rp > 0; rp--)

                   m.put(s.substring(i - rp - 1,  i - rp - 1 

                                       + 2 * rp + j), 1);

            m.put(s.substring(i, i + 1), 1);

        }

       

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

        // карта хеша

       System.out.println("Below are " + (m.size())

                           + " palindrome sub-strings");

         

       for (Map.Entry<String, Integer> ii:m.entrySet())

          System.out.println(ii.getKey());

    }

       

    // Драйвер программы

    public static void main(String args[])

    {

        palindromeSubStrs("abaaa");

    }

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

питон

# Программа Python Найти все различные палиндромные подстроки
# данной строки

  
# Функция для печати всех различных подстрок палиндрома s

def palindromeSubStrs(s):

    m = dict()

    n = len(s)

  

    # таблица для хранения результатов (2 строки для нечетных

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

    R = [[0 for x in xrange(n+1)] for x in xrange(2)]

  

    # Найти все подстроки палиндромов из заданного ввода

    # строка вставляет 'охранники' для легкой итерации

    s = "@" + s + "#"

  

    for j in xrange(2):

        rp = 0    # длина радиуса палиндрома

        R[j][0] = 0

  

        i = 1

        while i <= n:

  

            # Попытка расширить палиндром по центру

            while s[i - rp - 1] == s[i + j + rp]:

                rp += 1 # Увеличение длины палиндромной

                        # радиус, как и когда мы находим действительный палиндром

  

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

            # массив длины

            R[j][i] = rp

            k = 1

            while (R[j][i - k] != rp - k) and (k < rp):

                R[j][i+k] = min(R[j][i-k], rp - k)

                k += 1

            rp = max(rp - k, 0)

            i += k

  

    # снять охрану

    s = s[1:len(s)-1]

  

    # Поместите все полученные палиндромы в хэш-карту, чтобы

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

    m[s[0]] = 1

    for i in xrange(1,n):

        for j in xrange(2):

            for rp in xrange(R[j][i],0,-1):

                m[s[i - rp - 1 : i - rp - 1 + 2 * rp + j]] = 1

        m[s[i]] = 1

  

    # печать всех отдельных палиндромов из хэш-карты

    print "Below are " + str(len(m)) + " pali sub-strings"

    for i in m:

        print i

  
# Драйверная программа

palindromeSubStrs("abaaa")

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

C #

// C # программа для поиска всех отличных палиндромов
// подстроки данной строки

using System;

using System.Collections.Generic;

  

class GFG 

{

  

    // Функция для печати всех различных палиндромов

    // подстроки s

    public static void palindromeSubStrs(string s) 

    {

        // map <string, int> m;

        Dictionary < string,

        int > m = new Dictionary < string,

        int > ();

        int n = s.Length;

  

        // таблица для хранения результатов (2 строки для нечетных

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

        int[, ] R = new int[2, n + 1];

  

        // Найти все подстроки палиндромов из

        // заданную входную строку вставляем 'guards' в

        // легко повторяем по s

        s = "@" + s + "#";

        for (int j = 0; j <= 1; j++)

        {

            int rp = 0; // длина радиуса палиндрома

            R[j, 0] = 0;

            int i = 1;

            while (i <= n) 

            {

                  

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

                // у меня

                while (s[i - rp - 1] == s[i + j + rp])

  

                // Увеличиваем длину

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

                // когда мы находим Vaid Palindrome

                rp++;

  

                // Назначаем найденную палиндромную длину

                // в нечетную / четную длину массива

                R[j, i] = rp;

                int k = 1;

                while ((R[j, i - k] != rp - k) && k < rp)

                {

                    R[j, i + k] = Math.Min(R[j, i - k], rp - k);

                    k++;

                }

                rp = Math.Max(rp - k, 0);

                i += k;

            }

        }

  

        // убираем «охранников»

        s = s.Substring(1);

  

        // Поместить все полученные палиндромы в хэш-карту в

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

        if (!m.ContainsKey(s.Substring(0, 1))) 

            m.Add(s.Substring(0, 1), 1);

        else 

            m[s.Substring(0, 1)]++;

  

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

        {

            for (int j = 0; j <= 1; j++)

            for (int rp = R[j, i]; rp > 0; rp--) 

            {

                if (!m.ContainsKey(s.Substring(i - rp - 1, 2 * rp + j))) 

                    m.Add(s.Substring(i - rp - 1, 2 * rp + j), 1);

                else

                    m[s.Substring(i - rp - 1, 2 * rp + j)]++;

            }

  

            if (!m.ContainsKey(s.Substring(i, 1))) 

                m.Add(s.Substring(i, 1), 1);

            else

                m[s.Substring(i, 1)]++;

        }

  

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

        // карта хеша

        Console.WriteLine("Below are " + (m.Count));

  

        foreach(KeyValuePair < string, int > ii in m)

        Console.WriteLine(ii.Key);

    }

  

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

    public static void Main(string[] args) 

    {

        palindromeSubStrs("abaaa");

    }

}

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


Выход:

 Below are 5 palindrome sub-strings
a
aa
aaa
aba
b 

Аналогичная проблема:
Подсчитать все подстроки палиндрома в строке

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

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

Найти все различные палиндромные подстроки данной строки

0.00 (0%) 0 votes