Рубрики

Подсчитайте способы увеличения длины LCS двух строк на одну

Учитывая две строки символов нижнего алфавита, нам нужно найти количество способов вставить символ в первую строку, чтобы длина LCS обеих строк увеличилась на один.
Примеры:

Input : str1 = “abab”, str2 = “abc”
Output : 3
LCS length of given two strings is 2.
There are 3 ways of insertion in str1, 
to increase the LCS length by one which 
are enumerated below, 
str1 = “abcab”    str2 = “abc”  LCS length = 3
str1 = “abacb”    str2 = “abc”  LCS length = 3
str1 = “ababc”    str2 = “abc”  LCS length = 3

Input : str1 = “abcabc”, str2 = “abcd”
Output : 4

Идея состоит в том, чтобы попробовать все 26 возможных символов в каждой позиции первой строки, если длина str1 равна m, тогда новый символ может быть вставлен в (m + 1) позиции, теперь предположим, что в любое время символ c вставляется в i-ю позицию в str1 тогда мы сопоставим его со всеми позициями, имеющими символ c в str2. Предположим, что одной такой позицией является j, тогда, чтобы общая длина LCS была на одну больше, чем предыдущая, должно удовлетворять условие ниже,

LCS(str1[1, m], str2[1, n]) = LCS(str1[1, i],  str2[1, j-1]) + 
                              LCS(str1[i+1, m], str2[j+1, n])  

Вышеприведенное уравнение гласит, что сумма LCS подстрок суффикса и префикса при вставленном символе должна совпадать с общей суммой LCS строк, поэтому, когда один и тот же символ вставляется в первую строку, он увеличивает длину LCS на единицу.

В приведенном ниже коде два 2D-массива, lcsl и lcsr используются для хранения LCS префикса и суффикса строк соответственно. Способ заполнения этих 2D массивов можно найти здесь .
Пожалуйста, смотрите код ниже для лучшего понимания,

C ++

// C ++ программа для получения ряда способов увеличения
// LCS by 1
#include <bits/stdc++.h>

using namespace std;

  
#define M 26

  
// Утилита для получения целочисленной позиции ниже
// алфавит

int toInt(char ch)

{

    return (ch - 'a');

}

  
// Метод возвращает общее количество способов увеличить длину LCS на 1

int waysToIncreaseLCSBy1(string str1, string str2)

{

    int m = str1.length(), n = str2.length();

  

    // Заполняем позиции каждого символа в векторе

    vector<int> position[M];

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

        position[toInt(str2[i-1])].push_back(i);

  

    int lcsl[m + 2][n + 2];

    int lcsr[m + 2][n + 2];

  

    // Инициализация 2D массива по 0 значениям

    for (int i = 0; i <= m+1; i++)

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

            lcsl[i][j] = lcsr[i][j] = 0;

  

    // Заполняем массив LCS для префиксных подстрок

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

    {

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

        {

            if (str1[i-1] == str2[j-1])

                lcsl[i][j] = 1 + lcsl[i-1][j-1];

            else

                lcsl[i][j] = max(lcsl[i-1][j],

                                lcsl[i][j-1]);

        }

    }

  

    // Заполняем массив LCS для подстрок суффикса

    for (int i = m; i >= 1; i--)

    {

        for (int j = n; j >= 1; j--)

        {

            if (str1[i-1] == str2[j-1])

                lcsr[i][j] = 1 + lcsr[i+1][j+1];

            else

                lcsr[i][j] = max(lcsr[i+1][j],

                                 lcsr[i][j+1]);

        }

    }

  

    // Цикл для всех возможных позиций вставки

    // в первой строке

    int ways = 0;

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

    {

        // пробуем все возможные символы нижнего регистра

        for (char c='a'; c<='z'; c++)

        {

            // Теперь для каждого символа цикл

            // позиции символов во второй строке

            for (int j=0; j<position[toInt(c)].size(); j++)

            {

                int p = position[toInt(c)][j];

  

                // Если и левая, и правая подстроки

                // итого LCS затем увеличиваем результат на 1

                if (lcsl[i][p-1] + lcsr[i+1][p+1] == lcsl[m][n])

                    ways++;

            }

        }

    }

  

    return ways;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    string str1 = "abcabc";

    string str2 = "abcd";

    cout << waysToIncreaseLCSBy1(str1, str2);

    return 0;

}

Джава

// Java-программа для получения ряда способов увеличения
// LCS by 1

import java.util.*;

  

class GFG 

{

    static int M = 26;

  

    // Метод возвращает общее количество способов увеличения

    // длина LCS на 1

    static int waysToIncreaseLCSBy1(String str1,

                                    String str2) 

    {

        int m = str1.length(), n = str2.length();

  

        // Заполняем позиции каждого символа в векторе

        Vector<Integer>[] position = new Vector[M];

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

            position[i] = new Vector<>();

  

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

            position[str2.charAt(i - 1) - 'a'].add(i);

  

        int[][] lcsl = new int[m + 2][n + 2];

        int[][] lcsr = new int[m + 2][n + 2];

  

        // Инициализация 2D массива по 0 значениям

        for (int i = 0; i <= m + 1; i++)

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

                lcsl[i][j] = lcsr[i][j] = 0;

  

        // Заполняем массив LCS для префиксных подстрок

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

        {

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

            {

                if (str1.charAt(i - 1) == str2.charAt(j - 1))

                    lcsl[i][j] = 1 + lcsl[i - 1][j - 1];

                else

                    lcsl[i][j] = Math.max(lcsl[i - 1][j], 

                                          lcsl[i][j - 1]);

            }

        }

  

        // Заполняем массив LCS для подстрок суффикса

        for (int i = m; i >= 1; i--) 

        {

            for (int j = n; j >= 1; j--) 

            {

                if (str1.charAt(i - 1) == str2.charAt(j - 1))

                    lcsr[i][j] = 1 + lcsr[i + 1][j + 1];

                else

                    lcsr[i][j] = Math.max(lcsr[i + 1][j],

                                          lcsr[i][j + 1]);

            }

        }

  

        // Цикл для всех возможных позиций вставки

        // в первой строке

        int ways = 0;

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

        {

  

            // пробуем все возможные символы нижнего регистра

            for (char d = 0; d < 26; d++) 

            {

  

                // Теперь для каждого символа цикл

                // позиции символов во второй строке

                for (int j = 0; j < position[d].size(); j++)

                {

                    int p = position[d].elementAt(j);

  

                    // Если и левая, и правая подстроки

                    // итого LCS затем увеличиваем результат на 1

                    if (lcsl[i][p - 1] +

                        lcsr[i + 1][p + 1] == lcsl[m][n])

                        ways++;

                }

            }

        }

        return ways;

    }

  

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

    public static void main(String[] args) 

    {

        String str1 = "abcabc";

        String str2 = "abcd";

        System.out.println(waysToIncreaseLCSBy1(str1, str2));

    }

}

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

python3

# Python программа для получения количества способов увеличения
# LCS на 1

  

M = 26

  
# Метод возвращает общее количество способов увеличить длину LCS на 1

def waysToIncreaseLCSBy1(str1, str2):

    m = len(str1)

    n = len(str2)

  

    # Заполните позиции каждого символа в векторе

    # vector <int> position [M];

    position = [[] for i in range(M)]

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

        position[ord(str2[i-1])-97].append(i)

  

    # Инициализация 2D массива по 0 значениям

    lcsl = [[0 for i in range(n+2)] for j in range(m+2)]

    lcsr = [[0 for i in range(n+2)] for j in range(m+2)]

  

    # Заполнение массива LCS для префиксных подстрок

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

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

            if (str1[i-1] == str2[j-1]):

                lcsl[i][j] = 1 + lcsl[i-1][j-1]

            else:

                lcsl[i][j] = max(lcsl[i-1][j],

                                lcsl[i][j-1])

  

    # Заполнение массива LCS для подстрок суффикса

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

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

            if (str1[i-1] == str2[j-1]):

                lcsr[i][j] = 1 + lcsr[i+1][j+1]

            else:

                lcsr[i][j] = max(lcsr[i+1][j],

                                lcsr[i][j+1])

  

        # Цикл для всех возможных позиций вставки

        # в первой строке

    ways = 0

    for i in range(0, m+1,1):

        # Пробуем все возможные символы нижнего регистра

        for C in range(0, 26,1):

            # Теперь для каждого символа, цикл по тому же

            # позиции символов во второй строке

            for j in range(0, len(position[C]),1):

                p = position[C][j]

  

                # Если и левая, и правая подстроки

                # всего LCS, затем увеличьте результат на 1

                if (lcsl[i][p-1] + lcsr[i+1][p+1] == lcsl[m][n]):

                    ways += 1

    return ways

  

  
# Код драйвера для тестирования вышеуказанных методов

str1 = "abcabc"

str2 = "abcd"

print(waysToIncreaseLCSBy1(str1, str2))

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


Выход:

4


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

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

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

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

Подсчитайте способы увеличения длины LCS двух строк на одну

0.00 (0%) 0 votes