Считать отдельные вхождения как подпоследовательность

31.12.2019Динамическое программирование, Сортировка

Учитывая две строки S и T, найдите количество различных вхождений T в S в качестве подпоследовательности.

Примеры:

Input  : S = banana, T = ban
Output : 3
T appears in S as below three subsequences.
[ban], [ba  n], [b   an]

Input  : S = geeksforgeeks, T = ge
Output : 6
T appears in S as below three subsequences.
[ge], [     ge], [g e], [g    e] [g     e]
and [     g e]

Эта проблема может быть рекурсивно определена, как показано ниже.

// Returns count of subsequences of S that match T 
// m is length of T and n is length of S
subsequenceCount(S, T, n, m)

   // An empty string is subsequence of all.
   1) If length of T is 0, return 1.

   // Else no string can be a sequence of empty S.
   2) Else if S is empty, return 0.
    
   3) Else if last characters of S and T don't match,
      remove last character of S and recur for remaining
        return subsequenceCount(S, T, n-1, m)

   4) Else (Last characters match), the result is sum
      of two counts.
        
        // Remove last character of S and recur.
        a) subsequenceCount(S, T, n-1, m) + 

        // Remove last characters of S and T, and recur.
        b) subsequenceCount(S, T, n-1, m-1)

Поскольку в приведенном выше результате повторяемости есть перекрывающиеся подзадачи, мы можем применить подход динамического программирования для решения вышеуказанной проблемы. Мы создаем двумерный массив mat [m + 1] [n + 1], где m — длина строки T, а n — длина строки S. mat [i] [j] обозначает количество различных подпоследовательностей подстроки S (1. .i) и подстрока T (1..j), так что mat [m] [n] содержит наше решение.

C ++

/ * C / C ++ программа для подсчета количества раз появления S

как подпоследовательность в T * /

#include <bits/stdc++.h>

using namespace std;

int findSubsequenceCount(string S, string T)

{

int m = T.length(), n = S.length();

// T не может появиться как подпоследовательность в S

if (m > n)

return 0;

// mat [i] [j] хранит количество вхождений

// T (1..i) в S (1..j).

int mat[m + 1][n + 1];

// Инициализация первого столбца со всеми 0. Пустой

// строка не может иметь другую строку как последовательность

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

mat[i][0] = 0;

// Инициализация первой строки со всеми 1. Пустой

// строка является подпоследовательностью всех.

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

mat[0][j] = 1;

// Заполняем мат [] [] снизу вверх

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

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

// Если последние символы не совпадают, тогда значение

// совпадает со значением без последнего символа

// в с.

if (T[i - 1] != S[j - 1])

mat[i][j] = mat[i][j - 1];

// Остальное значение получается с учетом двух случаев.

// а) Все подстроки без последнего символа в S

// б) Все подстроки без последних символов в

// и то и другое.

else

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

}

/ * раскомментируйте это, чтобы напечатать матричный мат

for (int i = 1; i <= m; i ++, cout << endl)

для (int j = 1; j <= n; j ++)

cout << mat [i] [j] << ""; * /

return mat[m][n];

}

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

int main()

{

string T = "ge";

string S = "geeksforgeeks";

cout << findSubsequenceCount(S, T) << endl;

return 0;

}

Джава

// Java-программа для подсчета количества раз
// S появляется как подпоследовательность в T

import java.io.*;

class GFG {

static int findSubsequenceCount(String S, String T)

{

int m = T.length();

int n = S.length();

// T не может появиться как подпоследовательность в S

if (m > n)

return 0;

// mat [i] [j] сохраняет количество

// вхождения T (1..i) в S (1..j).

int mat[][] = new int[m + 1][n + 1];

// Инициализация первого столбца с

// все 0 Пустая строка не может иметь

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

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

mat[i][0] = 0;

// Инициализация первой строки со всеми 1.

// Пустая строка является подпоследовательностью всех.

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

mat[0][j] = 1;

// Заполняем мат [] [] снизу вверх

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

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

// Если последние символы не совпадают,

// тогда значение совпадает со значением

// без последнего символа в S.

if (T.charAt(i - 1) != S.charAt(j - 1))

mat[i][j] = mat[i][j - 1];

// Остальное значение получается с учетом двух случаев.

// а) Все подстроки без последнего символа в S

// б) Все подстроки без последних символов в

// и то и другое.

else

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

}

/ * раскомментируйте это, чтобы напечатать матричный мат

for (int i = 1; i <= m; i ++, cout << endl)

для (int j = 1; j <= n; j ++)

System.out.println (mat [i] [j] + ""); * /

return mat[m][n];

}

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

public static void main(String[] args)

{

String T = "ge";

String S = "geeksforgeeks";

System.out.println(findSubsequenceCount(S, T));

}

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

python3

# Python3 программа для подсчета количества раз
# S появляется как подпоследовательность в T

def findSubsequenceCount(S, T):

m = len(T)

n = len(S)

# T не может появиться как подпоследовательность в S

if m > n:

return 0

# mat [i] [j] хранит количество

# вхождения T (1..i) в S (1..j).

mat = [[0 for _ in range(n + 1)]

for __ in range(m + 1)]

# Инициализация первого столбца со всеми 0. Икс

# Пустая строка не может иметь другую

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

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

mat[i][0] = 0

# Инициализация первой строки со всеми 1.

# Пустая строка является подпоследовательностью всех.

for j in range(n + 1):

mat[0][j] = 1

# Заполнить мат [] [] снизу вверх

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

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

# Если последние символы не совпадают,

# тогда значение равно значению

# без последнего символа в S.

if T[i - 1] != S[j - 1]:

mat[i][j] = mat[i][j - 1]

# Остальное значение получается с учетом двух случаев.

# a) Все подстроки без последнего символа в S

# б) Все подстроки без последних символов в

# и то и другое.

else:

mat[i][j] = (mat[i][j - 1] +

mat[i - 1][j - 1])

return mat[m][n]

Код водителя

if __name__ == "__main__":

T = "ge"

S = "geeksforgeeks"

print(findSubsequenceCount(S, T))

# Этот код добавлен
# by vibhu4agarwal

C #

// C # программа для подсчета количества раз
// S появляется как подпоследовательность в T

using System;

class GFG {

static int findSubsequenceCount(string S, string T)

{

int m = T.Length;

int n = S.Length;

// T не может появиться как подпоследовательность в S

if (m > n)

return 0;

// mat [i] [j] сохраняет количество

// вхождения T (1..i) в S (1..j).

int[, ] mat = new int[m + 1, n + 1];

// Инициализация первого столбца с

// все 0 Пустая строка не может иметь

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

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

mat[i, 0] = 0;

// Инициализация первой строки со всеми 1.

// Пустая строка является подпоследовательностью всех.

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

mat[0, j] = 1;

// Заполняем мат [] [] снизу вверх

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

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

// Если последние символы не совпадают,

// тогда значение совпадает со значением

// без последнего символа в S.

if (T[i - 1] != S[j - 1])

mat[i, j] = mat[i, j - 1];

// Остальное значение получается с учетом двух случаев.

// а) Все подстроки без последнего символа в S

// б) Все подстроки без последних символов в

// и то и другое.

else

mat[i, j] = mat[i, j - 1] + mat[i - 1, j - 1];

}

/ * раскомментируйте это, чтобы напечатать матричный мат

for (int i = 1; i <= m; i ++, cout << endl)

для (int j = 1; j <= n; j ++)

System.out.println (mat [i] [j] + ""); * /

return mat[m, n];

}

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

public static void Main()

{

string T = "ge";

string S = "geeksforgeeks";

Console.WriteLine(findSubsequenceCount(S, T));

}

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

PHP

<?php
// PHP программа для подсчета количества раз
// S появляется как подпоследовательность в T * /

function findSubsequenceCount($S, $T)

{

$m = strlen($T); $n = strlen($S);

// T не может появиться как подпоследовательность в S

if ($m > $n)

return 0;

// mat [i] [j] сохраняет количество

// вхождения T (1..i) в S (1..j).

$mat = array(array());

// Инициализация первого столбца со всеми 0.

// Пустая строка не может иметь другую

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

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

$mat[$i][0] = 0;

// Инициализация первой строки со всеми 1.

// Пустая строка является подпоследовательностью всех.

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

$mat[0][$j] = 1;

// Заполняем мат [] [] снизу вверх

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

{

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

{

// Если последние символы не совпадают,

// тогда значение совпадает со значением

// без последнего символа в S.

if ($T[$i - 1] != $S[$j - 1])

$mat[$i][$j] = $mat[$i][$j - 1];

// Остальное значение получается с учетом двух случаев.

// а) Все подстроки без последнего символа в S

// б) Все подстроки без последних символов в

// и то и другое.

else

$mat[$i][$j] = $mat[$i][$j - 1] +

$mat[$i - 1][$j - 1];

}

/ * раскомментируйте это, чтобы напечатать матричный мат

for (int i = 1; i <= m; i ++, cout << endl)

для (int j = 1; j <= n; j ++)

cout << mat [i] [j] << ""; * /

return $mat[$m][$n];

}

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

$T = "ge";

$S = "geeksforgeeks";

echo findSubsequenceCount($S, $T) . "\n";

// Этот код добавлен
// Аканкша Рай

Выход:

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

Так как mat [i] [j] обращается к элементам только текущей строки и предыдущей строки, мы можем оптимизировать вспомогательное пространство, просто используя две строки, уменьшая пространство только с m * n до 2 * n.

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

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

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

Считать отдельные вхождения как подпоследовательность

0.00 (0%) 0 votes