Рубрики

Повторная подпоследовательность длиной 2 или более

По заданной строке найдите, существует ли какая-либо подпоследовательность длиной 2 или более, которая повторяется так, что две подпоследовательности не имеют одинаковый символ в одной и той же позиции, т. Е. Любой 0-й или 1-й символ в двух подпоследовательностях не должен не может иметь тот же индекс в исходной строке.

Пример:

Input: ABCABD
Output: Repeated Subsequence Exists (A B is repeated) 

Input: ABBB
Output: Repeated Subsequence Exists (B B is repeated)

Input: AAB
Output: Repeated Subsequence Doesn't Exist (Note that 
A B cannot be considered as repeating because B is at
same position in two subsequences).

Input: AABBC
Output: Repeated Subsequence Exists (A B is repeated)

Input: ABCDACB
Output: Repeated Subsequence Exists (A B is repeated)

Input: ABCD
Output: Repeated Subsequence Doesn't Exist

Проблема заключается в классической вариации самой длинной общей проблемы подпоследовательности . Мы обсудили решение динамического программирования здесь . Решение динамического программирования занимает O (n 2 ) время и пространство.

В этом посте обсуждается O (n) время и пространство.

Идея состоит в том, чтобы удалить все неповторяющиеся символы из строки и проверить, является ли полученная строка палиндромом или нет. Если оставшаяся строка является палиндромом, то она не повторяется, иначе есть повторение. Один особый случай, который мы должны обработать для таких входов, как «AAA», которые являются палиндромом, но их повторяющаяся подпоследовательность существует. Повторная подпоследовательность существует для строки палиндрома, если она имеет нечетную длину, а ее средняя буква совпадает с левой (или правой) буквой.

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

C ++

// C ++ программа для проверки повторения
// в строке существует подпоследовательность
#include <bits/stdc++.h>
#define MAX_CHAR 256

using namespace std;

  
// Функция для проверки, является ли строка str палиндромом

bool isPalindrome(char str[], int l, int h)

{

    // l и h - самые левые и правые углы строки

    // Продолжаем сравнивать символы, пока они одинаковые

    while (h > l)

        if (str[l++] != str[h--])

            return false;

  

    return true;

}

  
// Основная функция, которая проверяет, повторяется ли
// в строке существует подпоследовательность

int check(char str[])

{

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

    int n = strlen(str);

  

    // Создать массив для хранения всех символов и их

    // частоты в стр []

    int freq[MAX_CHAR] = { 0 };

  

    // Обходим входную строку и сохраняем частоты

    // всех символов в массиве freq [].

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

    {

        freq[str[i]]++;

  

        // Если количество символов больше 2

        // мы нашли повторение

        if (freq[str[i]] > 2)

            return true;

    }

  

    // Удалить на месте неповторяющиеся символы

    // из строки

    int k = 0;

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

        if (freq[str[i]] > 1)

            str[k++] = str[i];

    str[k] = '\0';

  

    // проверяем, является ли результирующая строка палиндромной

    if (isPalindrome(str, 0, k-1))

    {

        // особый случай - если длина нечетная

        // вернуть true, если средний символ

        // так же, как и предыдущий

        if (k & 1)

            return str[k/2] == str[k/2 - 1];

  

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

        return false;

    }

  

    // вернуть true, если строка не является палиндромом

    return true;

}

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

int main()

{

    char str[] = "ABCABD";

  

    if (check(str))

        cout << "Repeated Subsequence Exists";

    else

        cout << "Repeated Subsequence Doesn't Exists";

  

    return 0;

}

Джава

// Java-программа для проверки повторения
// в строке существует подпоследовательность

class GFG

{

    static int MAX_CHAR = 256;

  

    // Функция для проверки

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

    public static boolean isPalindrome(String str, 

                                       int l, int h) 

    {

          

        // l и h - самые левые и правые углы строки

        // Продолжаем сравнивать символы, пока они одинаковые

        while(h > l)

            if (str.charAt(l++) != str.charAt(h--))

                return false;

          

        return true;

    }

  

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

    // в строке существует подпоследовательность

    public static boolean check(String str)

    

          

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

        int n = str.length(); 

      

        // Создать массив для хранения всех символов

        // и их частоты в str []

        int[] freq = new int[MAX_CHAR]; 

      

        // Обходим входную строку и сохраняем частоты

        // всех символов в массиве freq [].

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

        

            freq[str.charAt(i)]++; 

      

            // Если количество символов больше 2

            // мы нашли повторение

            if (freq[str.charAt(i)] > 2

                return true

        

      

        // Удалить на месте неповторяющиеся символы

        // из строки

        int k = 0

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

            if (freq[str.charAt(i)] > 1

                str.replace(str.charAt(k++), 

                            str.charAt(i)); 

        str.replace(str.charAt(k), '\0');

  

        // проверяем, является ли результирующая строка палиндромной

        if (isPalindrome(str, 0, k - 1)) 

        

  

            // особый случай - если длина нечетная

            // вернуть true, если средний символ

            // так же, как и предыдущий

            if ((k & 1) == 1

            {

  

                // Проверено так, что

                // StringIndexOutOfBounds можно избежать

                if (k / 2 >= 1)

                    return (str.charAt(k / 2) == 

                            str.charAt(k / 2 - 1));

            }

      

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

            return false

        

      

        // вернуть true, если строка не является палиндромом

        return true

    }

      

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

    public static void main(String[] args)

    {

        String str = "ABCABD";

          

        if (check(str))

            System.out.println("Repeated Subsequence Exists");

        else

            System.out.println("Repeated Subsequence"

                               " Doesn't Exists"); 

    }

}

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

python3

# Python3 программа для проверки повторения
# подпоследовательность существует в строке

MAX_CHAR = 256

  
# Функция для проверки
# если String Str - палиндром

def isPalindrome(Str, l, h):

      

    # l и h - самые левые и правые углы Str

    # Продолжайте сравнивать персонажей, пока они одинаковы

    while (h > l):

        if (Str[l] != Str[h]):

            l += 1

            h -= 1

            return False

  

    return True

  
# Основная функция, которая проверяет, повторяется ли
# подпоследовательность существует в строке

def check(Str):

      

    # Найти длину входной строки

    n = len(Str)

  

    # Создать массив для хранения всех символов

    # и их частоты в Str []

    freq = [0 for i in range(MAX_CHAR)]

  

    # Пройти строку ввода и

    # хранить частоты всех персонажей

    # в массиве freq [].

    for i in range(n):

  

        freq[ord(Str[i])] += 1

  

        # Если количество символов больше 2

        # мы нашли повторение

        if (freq[ord(Str[i])] > 2):

            return True

  

    # Удалить на месте неповторяющиеся символы

    # из строки

    k = 0

    for i in range(n):

        if (freq[ord(Str[i])] > 1):

            Str[k] = Str[i]

            k += 1

    Str[k] = '\0'

  

    # проверить, является ли результирующая строка палиндромной

    if (isPalindrome(Str, 0, k - 1)):

          

        # особый случай - если длина нечетная

        # вернуть true, если средний символ

        # такой же, как предыдущий

        if (k & 1):

            return Str[k // 2] == Str[k // 2 - 1]

  

        # вернуть false, если String является палиндромом

        return False

  

    # вернуть true, если строка не является палиндромом

    return True

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

S = "ABCABD"

Str = [i for i in S]

  

if (check(Str)):

    print("Repeated Subsequence Exists")

else:

    print("Repeated Subsequence Doesn't Exists")

  
# Этот код предоставлен Мохитом Кумаром

C #

// C # программа для проверки повторения
// в строке существует подпоследовательность

using System;

      

class GFG

{

    static int MAX_CHAR = 256;

  

    // Функция для проверки

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

    public static Boolean isPalindrome(String str, 

                                    int l, int h) 

    {

          

        // l и h - самые левые и правые углы строки

        // Продолжаем сравнивать символы, пока они одинаковые

        while(h > l)

            if (str[l++] != str[h--])

                return false;

          

        return true;

    }

  

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

    // в строке существует подпоследовательность

    public static Boolean check(String str)

    

          

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

        int n = str.Length; 

      

        // Создать массив для хранения всех символов

        // и их частоты в str []

        int[] freq = new int[MAX_CHAR]; 

      

        // Обходим входную строку и сохраняем частоты

        // всех символов в массиве freq [].

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

        

            freq[str[i]]++; 

      

            // Если количество символов больше 2

            // мы нашли повторение

            if (freq[str[i]] > 2) 

                return true

        

      

        // Удалить на месте неповторяющиеся символы

        // из строки

        int k = 0; 

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

            if (freq[str[i]] > 1) 

                str.Replace(str[k++], 

                            str[i]); 

        str.Replace(str[k], '\0');

  

        // проверяем, является ли результирующая строка палиндромной

        if (isPalindrome(str, 0, k - 1)) 

        

  

            // особый случай - если длина нечетная

            // вернуть true, если средний символ

            // так же, как и предыдущий

            if ((k & 1) == 1) 

            {

  

                // Проверено так, что

                // StringIndexOutOfBounds можно избежать

                if (k / 2 >= 1)

                    return (str[k / 2] == 

                            str[k / 2 - 1]);

            }

      

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

            return false

        

      

        // вернуть true, если строка не является палиндромом

        return true

    }

      

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

    public static void Main(String[] args)

    {

        String str = "ABCABD";

          

        if (check(str))

            Console.WriteLine("Repeated Subsequence Exists");

        else

            Console.WriteLine("Repeated Subsequence"

                            " Doesn't Exists"); 

    }

}

  
// Этот код предоставлен Принчи Сингхом


Выход :

Repeated Subsequence Exists

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Повторная подпоследовательность длиной 2 или более

0.00 (0%) 0 votes