Рубрики

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

Учитывая две строки 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";

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


Выход:

6


Сложность времени:
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