Рубрики

Подсчитать палиндромные характеристики струны

Учитывая строку s длины n, подсчитайте количество подстрок, имеющих различные типы палиндромных характеристик.
Палиндромная характеристика — это число k-палиндромов в строке, где k лежит в диапазоне [0, n).
Строка является 1-палиндромом (или просто палиндромом) тогда и только тогда, когда она читает то же самое, что и обратное чтение.
Строка является k-палиндромом (k> 1) тогда и только тогда, когда:
1. Его левая половина равна его правой половине.
2. Его левая половина и правая половина должны быть непустыми (k — 1) -палиндромом. Левая половина строки длины 't' является ее префиксом длины ⌊t / 2⌋, а правая половина — суффиксом той же длины.
Примечание. Каждая подстрока считается столько раз, сколько она появляется в строке. Например, в строке «aaa» подстрока «a» появляется 3 раза.

Примеры :

Input : abba
Output : 6 1 0 0
Explanation : 
"6" 1-palindromes = "a", "b", "b", "a", "bb", "abba".
"1" 2-palindrome = "bb". Because "b" is 1-palindrome 
and "bb" has both left and right parts equal. 
"0" 3-palindrome and 4-palindrome.

Input : abacaba
Output : 12 4 1 0 0 0 0
Explanation : 
"12" 1-palindromes = "a", "b", "a", "c", "a", "b", 
"a", "aba", "aca", "aba", "bacab", "abacaba".
"4" 2-palindromes = "aba", "aca", "aba", "abacaba". 
Because "a" and "aba" are 1-palindromes.
NOTE :  "bacab" is not 2-palindrome as "ba" 
is not 1-palindrome. "1" 3-palindrome = "abacaba". 
Because is "aba" is 2-palindrome. "0" other 
k-pallindromes where 4 < = k < = 7.

Подход: возьмите строку s и скажите, что это 1-палиндром, и проверка ее левой половины также оказывается 1-палиндромом, тогда очевидно, что ее правая часть всегда будет равна левой части (так как строка также является 1- палиндром) делает исходную строку 2-палиндромом. Теперь, аналогично, проверяя левую половину строки, она также оказывается 1-палиндромом, затем она превращает левую половину в 2-палиндром и, следовательно, превращая исходную строку в 3-палиндром и так далее, проверяя ее до остался только 1 алфавит или часть не является 1-палиндромом.
Давайте возьмем строку = «абакаба». Как известно, «абакаба» — это 1-палиндром. Таким образом, при проверке его левой половины «aba», который также является 1-палиндромом, он делает «abacaba» 2-палиндромом. Затем проверьте левую половину «аба» «а», которая также является 1-палиндромом. Таким образом, это делает «аба» 2-палиндромом, а «аба» делает «абакабу» 3-палиндромом. Другими словами, если строка является k-палиндромом, то это также (k-1) -палиндром, (k-2) -палиндром и так далее до 1-палиндрома. Код для того же самого дан ниже, который сначала проверяет каждую подстроку, является ли это палиндромом или нет, и затем подсчитывает число k-палиндромных подстрок рекурсивно в логарифмическом времени.

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

C ++

// Программа на C ++, которая считает разные
// палиндромные характеристики струны.
#include <bits/stdc++.h>

using namespace std;

  

const int MAX_STR_LEN = 1000;

  

bool P[MAX_STR_LEN][MAX_STR_LEN];

int Kpal[MAX_STR_LEN];

  
// функция C ++, которая проверяет, является ли
// подстрока str [i..j] данной строки
// палиндром или нет.

void checkSubStrPal(string str, int n)

{

  

    // P [i] [j] = true, если подстрока str

    // [i..j] - палиндром, иначе ложь

    memset(P, false, sizeof(P));

  

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

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

        P[i][i] = true;

  

    // палиндром длины 2

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

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

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

  

    // Палиндромы длиной более 2.

    // Этот цикл похож на Matrix Chain

    // Умножение. Начнем с разрыва

    // длина 2 и заполнить таблицу P таким образом, чтобы

    // разрыв между начальным и конечным индексами

    // увеличивает один за другим внешний цикл.

    for (int gap = 2; gap < n; gap++)

    {

  

        // Выбрать начальную точку для текущего разрыва

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

        {

  

            // Установить конечную точку

            int j = gap + i;

  

            // Если текущей строкой является палиндром

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

                P[i][j] = true;

        }

    }

}

  
// функция C ++, которая рекурсивно
// считает, что строка str [i..j]
// k-палиндромная строка или нет.

void countKPalindromes(int i, int j, int k)

{

    // завершаем условие для

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

    if (i == j)

    {

        Kpal[k]++;

        return;

    }

  

    // завершаем условие для

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

    if (P[i][j] == false)

        return;

  

    // увеличивает счетчик для

    // строка, если это k-палиндром.

    Kpal[k]++;

  

    // середина указатель середины

    // строка str [i ... j].

    int mid = (i + j) / 2;

  

    // если длина строки

    // (j - i + 1) нечетно

    // вычесть одно из середины

    // иначе если даже тогда без изменений.

    if ((j - i + 1) % 2 == 1)

        mid--;

  

    // если строка k-палиндром

    // тогда мы проверяем, если это

    // (k + 1) - палиндром или нет

    // просто отправляю одну из половины

    // строка в Count_k_Palindrome

    // функция.

    countKPalindromes(i, mid, k + 1);

}

  

void printKPalindromes(string s)

{

  

    // Количество k-палиндромов равно

    // к нулю изначально.

    memset(Kpal, 0, sizeof(Kpal));

  

    // Находим все палиндромные

    // подстроки данной строки

    int n = s.length();

    checkSubStrPal(s, n);

  

    // подсчитываем k-палиндромы для каждого и

    // каждая подстрока данной строки. ,

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

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

            countKPalindromes(j, j + i, 1);

  

    // Выводим число К-палиндромов

    // подстроки данной строки.

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

        cout << Kpal[i] << " ";

    cout << "\n";

}

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

int main()

{

    string s = "abacaba";

    printKPalindromes(s);

    return 0;

}

Джава

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

import java.io.*;

  

class GFG

{

    static int MAX_STR_LEN = 1000;

      

    static boolean P[][] = 

           new boolean[MAX_STR_LEN][MAX_STR_LEN];

    static int []Kpal = 

           new int[MAX_STR_LEN];

      

    // функция, которая проверяет

    // есть ли подстрока

    // str [i..j] данного

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

    static void checkSubStrPal(String str, 

                               int n)

    {

      

        // P [i, j] = true, если подстрока

        // str [i..j] - палиндром,

        // иначе ложь

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

        {

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

                P[i][j] = false;

            Kpal[i] = 0;

        }

          

        // палиндром из

        // одиночная длина

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

            P[i][i] = true;

      

        // палиндром из

        // длина 2

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

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

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

      

        // Палиндромы длины

        // больше чем 2. Этот цикл

        // похож на матрицу

        // Цепное умножение.

        // Начнем с пробела

        // длина 2 и заполнение таблицы P

        // таким образом, что разрыв между

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

        // увеличивает по одному

        // внешний цикл

        for (int gap = 2; gap < n; gap++)

        {

      

            // Выберите начальную точку

            // для текущего разрыва

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

            {

      

                // Установить конечную точку

                int j = gap + i;

      

                // Если текущая строка

                // палиндром

                if (str.charAt(i) == str.charAt(j) && 

                                     P[i + 1][j - 1])

                    P[i][j] = true;

            }

        }

    }

      

    // Функция, которая рекурсивно

    // считает, что строка str [i..j]

    // k-палиндромная строка или нет.

    static void countKPalindromes(int i, int j, 

                                  int k)

    {

        // завершающее условие

        // для строки, которая

        // к-палиндром.

        if (i == j)

        {

            Kpal[k]++;

            return;

        }

      

        // завершаем условие

        // строка, которая не является

        // к-палиндром.

        if (P[i][j] == false)

            return;

      

        // увеличивает счетчик

        // для строки, если она

        // это k-палиндром.

        Kpal[k]++;

      

        // середина указатель середины

        // строка str [i ... j].

        int mid = (i + j) / 2;

      

        // если длина строки, которая

        // is (j - i + 1) нечетно чем

        // мы должны вычесть один

        // из середины, если даже тогда

        // без изменений.

        if ((j - i + 1) % 2 == 1)

            mid--;

      

        // если строка k-палиндром

        // тогда мы проверяем, если это

        // (k + 1) - палиндром или нет

        // просто отправив одну из

        // половина строки до

        // Функция Count_k_Palindrome.

        countKPalindromes(i, mid, k + 1);

    }

      

    static void printKPalindromes(String s)

    {

        // Находим все палиндромные

        // подстроки данной строки

        int n = s.length();

        checkSubStrPal(s, n);

      

        // подсчитываем k-палиндромы для

        // каждая подстрока

        // данной строки. ,

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

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

                countKPalindromes(j, j + i, 1);

      

        // Вывести номер

        // К-палиндромные подстроки

        // данной строки.

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

            System.out.print(Kpal[i] + " ");

        System.out.println();

    }

      

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

    public static void main(String args[])

    {

        String s = "abacaba";

        printKPalindromes(s);

    }

}

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)

python3

# Python программа, которая считает
# разные палиндромные
# характеристики строки.

MAX_STR_LEN = 1000;

  

P = [[0 for x in range(MAX_STR_LEN)] 

        for y in range(MAX_STR_LEN)] ;

  

for i in range(0, MAX_STR_LEN) :

    for j in range(0, MAX_STR_LEN) :

        P[i][j] = False;

          

Kpal = [0] * MAX_STR_LEN;

      
# def который проверяет
# является ли подстрока [i..j]
# данного является
# палиндром или нет.

def checkSubStrPal(str, n) :

  

    global P, Kpal, MAX_STR_LEN;

              

    # P [i, j] = True, если substr

    # [i..j] - палиндром,

    # еще False

    for i in range(0, MAX_STR_LEN) :

  

        for j in range(0, MAX_STR_LEN) :

            P[i][j] = False;

        Kpal[i] = 0;

      

    # палиндром из

    # одна длина

    for i in range(0, n) :

        P[i][i] = True;

  

    # палиндром из

    # длина 2

    for i in range(0, n - 1) :

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

            P[i][i + 1] = True;

  

    # Палиндромы длины больше

    # затем 2. Этот цикл похож

    # к умножению цепочки матриц.

    # Начнем с пробела длины

    # 2 и заполните таблицу P таким образом,

    # этот разрыв между началом и

    # конечные индексы увеличивают на один

    # по одному по внешнему циклу.

    for gap in range(2, n) :

  

        # Выберите начальную точку

        # для текущего разрыва

        for i in range(0, n - gap) :

  

            # Установить конечную точку

            j = gap + i;

  

            # Если текущая строка

            # палиндром

            if (str[i] == str[j] and 

                P[i + 1][j - 1]) :

                P[i][j] = True;

  
# Python def, который
# рекурсивно считается, если
# a str [i..j] является
# к-палиндромная или нет.

def countKPalindromes(i, j, k) :

  

    global Kpal, P;

      

    # завершающее условие

    # для которого является

    # к-палиндром.

    if (i == j) :

      

        Kpal[k] = Kpal[k] + 1;

        return;

  

    # завершающее условие

    # для которого не является

    # к-палиндром.

    if (P[i][j] == False) :

        return;

  

    # увеличивает счетчик

    # если это

    # к-палиндром.

    Kpal[k] = Kpal[k] + 1;

  

    # mid - средний указатель

    № улицы [я ... J].

    mid = int((i + j) / 2);

  

    # если длина которого

    # (j - i + 1) нечетно чем

    # мы должны вычесть один

    # от середины, если даже

    # тогда без изменений.

    if ((j - i + 1) % 2 == 1) :

        mid = mid - 1;

  

    # если к-палиндром

    # тогда мы проверяем, если это

    # (k + 1) - палиндром или нет

    # просто отправив любой из

    # одна половина к

    # Count_k_Palindrome def.

    countKPalindromes(i, mid, k + 1);

  

def printKPalindromes(s) :

  

    global P, Kpal, MAX_STR_LEN;

              

    # Нахождение всех палиндромных

    # подстроки данной строки

    n = len(s);

    checkSubStrPal(s, n);

  

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

    # для каждого саба

    # данной строки. ,

    for i in range(0, n) :

        for j in range(0, n - i) :

            countKPalindromes(j, j + i, 1);

  

    # Выведите количество

    # К-палиндромные подстроки

    # данной строки.

    for i in range(1, n + 1) :

        print (Kpal[i], end=" ");

    print();

  

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

s = "abacaba";

printKPalindromes(s);

  
# Этот код предоставлен
# Маниш Шоу (manishshaw1)

C #

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

using System;

  

class GFG

{

    static int MAX_STR_LEN = 1000;

      

    static bool [,]P = new bool[MAX_STR_LEN, 

                                MAX_STR_LEN];

    static int []Kpal = new int[MAX_STR_LEN];

      

    // функция, которая проверяет,

    // подстрока str [i..j] из

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

    static void checkSubStrPal(string str, 

                               int n)

    {

      

        // P [i, j] = true, если подстрока str

        // [i..j] - палиндром, иначе ложь

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

        {

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

                P[i, j] = false;

            Kpal[i] = 0;

        }

          

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

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

            P[i, i] = true;

      

        // палиндром длины 2

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

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

                P[i, i + 1] = true;

      

        // Палиндромы длины больше

        // затем 2. Этот цикл похож

        // к матричному умножению.

        // Начнем с пробела длины 2

        // и заполняем таблицу P таким образом, чтобы

        // разрыв между началом и окончанием

        // индексы увеличиваются один за другим

        // внешний цикл

        for (int gap = 2; gap < n; gap++)

        {

      

            // Выберите начальную точку

            // для текущего разрыва

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

            {

      

                // Установить конечную точку

                int j = gap + i;

      

                // Если текущая строка

                // палиндром

                if (str[i] == str[j] && 

                        P[i + 1, j - 1])

                    P[i, j] = true;

            }

        }

    }

      

    // функция C ++, которая рекурсивно

    // считает, что строка str [i..j]

    // k-палиндромная строка или нет.

    static void countKPalindromes(int i, int j, 

                                  int k)

    {

        // завершаем условие для

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

        if (i == j)

        {

            Kpal[k]++;

            return;

        }

      

        // завершаем условие

        // строка, которая не является

        // к-палиндром.

        if (P[i, j] == false)

            return;

      

        // увеличивает счетчик для

        // строка, если это k-палиндром.

        Kpal[k]++;

      

        // середина указатель середины

        // строка str [i ... j].

        int mid = (i + j) / 2;

      

        // если длина строки

        // (j - i + 1) нечетно

        // вычесть одно из середины

        // иначе если даже тогда без изменений.

        if ((j - i + 1) % 2 == 1)

            mid--;

      

        // если строка k-палиндром

        // тогда мы проверяем, если это

        // (k + 1) - палиндром или нет

        // просто отправив одну из

        // половина строки до

        // Функция Count_k_Palindrome.

        countKPalindromes(i, mid, k + 1);

    }

      

    static void printKPalindromes(string s)

    {

        // Находим все палиндромные

        // подстроки данной строки

        int n = s.Length;

        checkSubStrPal(s, n);

      

        // подсчитываем k-палиндромы для каждого и

        // каждая подстрока данной строки. ,

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

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

                countKPalindromes(j, j + i, 1);

      

        // Выводим число К-палиндромов

        // подстроки данной строки.

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

            Console.Write(Kpal[i] + " ");

        Console.WriteLine();

    }

      

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

    static void Main()

    {

        string s = "abacaba";

        printKPalindromes(s);

    }

}

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)

PHP

<?php
// PHP-программа, которая считает
// разные палиндромные
// характеристики строки.

$MAX_STR_LEN = 1000;

  

$P = array(array());

$Kpal = array_fill(0, $MAX_STR_LEN, 0);

  

for($i = 0; $i < $MAX_STR_LEN; $i++) 

{

    for($j = 0; $j < $MAX_STR_LEN; $j++)

        $P[$i][$j] = false;

}

      
// функция, которая проверяет
// есть ли подстрока [i..j]
// данного является
// палиндром или нет.

function checkSubStrPal($str

                        $n)

{

    global $P, $Kpal

           $MAX_STR_LEN;

             

    // P [i, j] = true, если substr

    // [i..j] - палиндром, иначе ложь

    for ($i = 0; 

         $i < $MAX_STR_LEN; $i++) 

    {

        for ($j = 0; 

             $j < $MAX_STR_LEN; $j++)

            $P[$i][$j] = false;

        $Kpal[$i] = 0;

    }

      

    // палиндром из

    // одиночная длина

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

        $P[$i][$i] = true;

  

    // палиндром из

    // длина 2

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

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

            $P[$i][$i + 1] = true;

  

    // Палиндромы длины больше

    // затем 2. Этот цикл похож

    // к матричному умножению.

    // Начнем с пробела длины

    // 2 и заполняем таблицу P способом

    // этот разрыв между началом и

    // конечные индексы увеличивают

    // по одному по внешнему циклу.

    for ($gap = 2; $gap < $n; $gap++)

    {

        // Выберите начальную точку

        // для текущего разрыва

        for ($i = 0; 

             $i < $n - $gap; $i++)

        

            // Установить конечную точку

            $j = $gap + $i;

  

            // Если текущая строка

            // палиндром

            if ($str[$i] == $str[$j] && 

                    $P[$i + 1][$j - 1])

                $P[$i][$j] = true;

        }

    }

}

  
// PHP-функция, которая
// рекурсивно считает если
// str [i..j] является
// к-палиндромный или нет.

function countKPalindromes($i, $j, $k)

{

    global $Kpal, $P;

      

    // завершаем условие для

    // который является k-палиндромом.

    if ($i == $j)

    {

        $Kpal[$k]++;

        return;

    }

  

    // завершающее условие

    // для которого не

    // к-палиндром.

    if ($P[$i][$j] == false)

        return;

  

    // увеличивает счетчик

    // если это

    // к-палиндром.

    $Kpal[$k]++;

  

    // середина указатель середины

    // Стр [i ... j].

    $mid = ($i + $j) / 2;

  

    // если длина которого

    // (j - i + 1) нечетно чем

    // мы должны вычесть один

    // из середины, если даже

    // тогда без изменений.

    if (($j - $i + 1) % 2 == 1)

        $mid--;

  

    // если к-палиндром

    // тогда мы проверяем, если это

    // (k + 1) - палиндром или нет

    // просто отправив любой из

    // одна половина к

    // Функция Count_k_Palindrome.

    countKPalindromes($i, $mid,

                      $k + 1);

}

  

function printKPalindromes($s)

{

    global $P, $Kpal

           $MAX_STR_LEN;

             

    // Находим все палиндромные

    // подстроки данной строки

    $n = strlen($s);

    checkSubStrPal($s, $n);

  

    // подсчитываем k-палиндромы

    // для каждого саба

    // данной строки. ,

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

        for ($j = 0; $j < $n - $i; $j++)

            countKPalindromes($j, $j

                              $i, 1);

  

    // Вывести номер

    // К-палиндромные подстроки

    // данной строки.

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

        echo ($Kpal[$i] . " ");

    echo("\n");

}

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

$s = "abacaba";

printKPalindromes($s);

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)
?>

Выход :

12 4 1 0 0 0 0

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

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

Подсчитать палиндромные характеристики струны

0.00 (0%) 0 votes