Найти, сколько раз строка встречается как подпоследовательность в данной строке

Опубликовано: 20 Января, 2022

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

Примеры:

 Вход: 
строка a = "GeeksforGeeks"
строка b = "Gks"

Выход: 4

Объяснение: 
Четыре строки - (Проверочные символы выделены жирным шрифтом )
G ee ks для гиков
G eeksforGee кс
G ee k sforGeek s
Geeksfor G ee ks
Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

Если внимательно проанализировать данную проблему, то можно увидеть, что ее легко разделить на подзадачи. Идея состоит в том, чтобы обрабатывать все символы обеих строк по очереди, глядя либо слева, либо справа. Давайте перейдем из правого угла, есть две возможности для каждой пары перемещаемых символов.

 m: Длина str1 (первая строка)
n: длина str2 (вторая строка)

Если последние символы двух строк совпадают, 
   1. Считаем последние символы и подсчитываем оставшиеся 
      струны. Итак, мы повторяемся для длин m-1 и n-1. 
   2. Мы можем игнорировать последний символ первой строки и 
      рекурсию для длин m-1 и n.
еще 
Если последние символы не совпадают, 
   Мы игнорируем последний символ первой строки и 
   рекурсию для длин m-1 и n.

Below is the implementation of above Naive recursive solution – 

C++

// A Naive recursive C++ program to find the number of
// times the second string occurs in the first string,
// whether continuous or discontinuous
#include <iostream>
using namespace std;
 
// Recursive function to find the number of times
// the second string occurs in the first string,
// whether continuous or discontinuous
int count(string a, string b, int m, int n)
{
    // If both first and second string is empty,
    // or if second string is empty, return 1
    if ((m == 0 && n == 0) || n == 0)
        return 1;
 
    // If only first string is empty and second
    // string is not empty, return 0
    if (m == 0)
        return 0;
 
    // If last characters are same
    // Recur for remaining strings by
    // 1. considering last characters of both strings
    // 2. ignoring last character of first string
    if (a[m - 1] == b[n - 1])
        return count(a, b, m - 1, n - 1) +
               count(a, b, m - 1, n);
    else
        // If last characters are different, ignore
        // last char of first string and recur for
        // remaining string
        return count(a, b, m - 1, n);
}
 
// Driver code
int main()
{
    string a = "GeeksforGeeks";
    string b = "Gks";
 
    cout << count(a, b, a.size(), b.size()) << endl;
 
    return 0;
}

Java

// A Naive recursive java program to find the number of
// times the second string occurs in the first string,
// whether continuous or discontinuous
import java.io.*;
 
class GFG
{
     
    // Recursive function to find the number of times
    // the second string occurs in the first string,
    // whether continuous or discontinuous
    static int count(String a, String b, int m, int n)
    {
        // If both first and second string is empty,
        // or if second string is empty, return 1
        if ((m == 0 && n == 0) || n == 0)
            return 1;
     
        // If only first string is empty and
        // second string is not empty, return 0
        if (m == 0)
            return 0;
     
        // If last characters are same
        // Recur for remaining strings by
        // 1. considering last characters of
        // both strings
        // 2. ignoring last character of
        // first string
        if (a.charAt(m - 1) == b.charAt(n - 1))
            return count(a, b, m - 1, n - 1) +
                   count(a, b, m - 1, n);
        else
            // If last characters are different, 
            // ignore last char of first string
            // and recur for  remaining string
            return count(a, b, m - 1, n);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        String a = "GeeksforGeeks";
        String b = "Gks";
        System.out.println( count(a, b, a.length(), b.length())) ;
     
    }
}
 
// This code is contributed by vt_m

Python 3

# A Naive recursive Python program
# to find the number of times the
# second string occurs in the first
# string, whether continuous or
# discontinuous
 
# Recursive function to find the
# number of times the second string
# occurs in the first string,
# whether continuous or discontinuous
def count(a, b, m, n):
 
    # If both first and second string
    # is empty, or if second string
    # is empty, return 1
    if ((m == 0 and n == 0) or n == 0):
        return 1
 
    # If only first string is empty
    # and second string is not empty,
    # return 0
    if (m == 0):
        return 0
 
    # If last characters are same
    # Recur for remaining strings by
    # 1. considering last characters
    #    of both strings
    # 2. ignoring last character
    #    of first string
    if (a[m - 1] == b[n - 1]):
        return (count(a, b, m - 1, n - 1) +
                count(a, b, m - 1, n))
    else:
         
        # If last characters are different,
        # ignore last char of first string
        # and recur for remaining string
        return count(a, b, m - 1, n)
 
# Driver code
a = "GeeksforGeeks"
b = "Gks"
 
print(count(a, b, len(a),len(b)))
 
# This code is contributed by ash264

C#

// A Naive recursive C# program to find the number of
// times the second string occurs in the first string,
// whether continuous or discontinuous
using System;
  
class GFG
{
      
    // Recursive function to find the number of times
    // the second string occurs in the first string,
    // whether continuous or discontinuous
    static int count(string a, string b, int m, int n)
    {
        // If both first and second string is empty,
        // or if second string is empty, return 1
        if ((m == 0 && n == 0) || n == 0)
            return 1;
      
        // If only first string is empty and
        // second string is not empty, return 0
        if (m == 0)
            return 0;
      
        // If last characters are same
        // Recur for remaining strings by
        // 1. considering last characters of
        // both strings
        // 2. ignoring last character of
        // first string
        if (a[m - 1] == b[n - 1])
            return count(a, b, m - 1, n - 1) +
                   count(a, b, m - 1, n);
        else
            // If last characters are different, 
            // ignore last char of first string
            // and recur for  remaining string
            return count(a, b, m - 1, n);
    }
      
    // Driver code
    public static void Main ()
    {
        string a = "GeeksforGeeks";
        string b = "Gks";
        Console.Write( count(a, b, a.Length, b.Length) );
      
    }
}
  
// This code is contributed by nitin mittal

PHP

<?php
// A Naive recursive PHP program to find the number of
// times the second string occurs in the first string,
// whether continuous or discontinuous
  
// Recursive function to find the number of times
// the second string occurs in the first string,
// whether continuous or discontinuous
function count_1($a, $b, $m, $n)
{
    // If both first and second string is empty,
    // or if second string is empty, return 1
    if (($m == 0 && $n == 0) || $n == 0)
        return 1;
  
    // If only first string is empty and second
    // string is not empty, return 0
    if ($m == 0)
        return 0;
  
    // If last characters are same
    // Recur for remaining strings by
    // 1. considering last characters of both strings
    // 2. ignoring last character of first string
    if ($a[$m - 1] == $b[$n - 1])
        return count_1($a, $b, $m - 1, $n - 1) +
               count_1($a, $b, $m - 1, $n);
    else
        // If last characters are different, ignore
        // last char of first string and recur for
        // remaining string
        return count_1($a, $b, $m - 1, $n);
}
  
// Driver code
 
$a = "GeeksforGeeks";
$b = "Gks";
echo count_1($a, $b, strlen($a), strlen($b)) ." ";
return 0;
?>

Javascript

<script>
// A Naive recursive javascript program to find the number of
// times the second string occurs in the first string,
// whether continuous or discontinuous
 
    // Recursive function to find the number of times
    // the second string occurs in the first string,
    // whether continuous or discontinuous
    function count( a,  b , m , n)
    {
     
        // If both first and second string is empty,
        // or if second string is empty, return 1
        if ((m == 0 && n == 0) || n == 0)
            return 1;
 
        // If only first string is empty and
        // second string is not empty, return 0
        if (m == 0)
            return 0;
 
        // If last characters are same
        // Recur for remaining strings by
        // 1. considering last characters of
        // both strings
        // 2. ignoring last character of
        // first string
        if (a[m - 1] == b[n - 1])
            return count(a, b, m - 1, n - 1) + count(a, b, m - 1, n);
        else
         
            // If last characters are different,
            // ignore last char of first string
            // and recur for remaining string
            return count(a, b, m - 1, n);
    }
 
    // Driver code
    var a = "GeeksforGeeks";
    var b = "Gks";
    document.write(count(a, b, a.length, b.length));
 
// This code is contributed by Amit Katiyar
</script>

Выход:

4

Временная сложность приведенного выше решения экспоненциальна. Если мы внимательно проанализируем, то увидим, что многие подзадачи решаются снова и снова. Поскольку одни и те же подзадачи вызываются снова, эта задача имеет свойство перекрытия подзадач. Таким образом, проблема имеет оба свойства (см. Это и это) задачи динамического программирования. Подобно другим типичным задачам динамического программирования, повторных вычислений одних и тех же подзадач можно избежать, создав временный массив, в котором хранятся результаты подзадач.

Below is its implementation using Dynamic Programming – 

C++

// A Dynamic Programming based C++ program to find the
// number of times the second string occurs in the first
// string, whether continuous or discontinuous
#include <iostream>
using namespace std;
 
// Iterative DP function to find the number of times
// the second string occurs in the first string,
// whether continuous or discontinuous
int count(string a, string b)
{
    int m = a.length();
    int n = b.length();
 
    // Create a table to store results of sub-problems
    int lookup[m + 1][n + 1] = { { 0 } };
 
    // If first string is empty
    for (int i = 0; i <= n; ++i)
        lookup[0][i] = 0;
 
    // If second string is empty
    for (int i = 0; i <= m; ++i)
        lookup[i][0] = 1;
 
    // Fill lookup[][] in bottom up manner
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            // If last characters are same, we have two
            // options -
            // 1. consider last characters of both strings
            //    in solution
            // 2. ignore last character of first string
            if (a[i - 1] == b[j - 1])
                lookup[i][j] = lookup[i - 1][j - 1] +
                               lookup[i - 1][j];
                 
            else
                // If last character are different, ignore
                // last character of first string
                lookup[i][j] = lookup[i - 1][j];
        }
    }
 
    return lookup[m][n];
}
 
// Driver code
int main()
{
    string a = "GeeksforGeeks";
    string b = "Gks";
 
    cout << count(a, b);
 
    return 0;
}

Java

// A Dynamic Programming based
// Java program to find the
// number of times the second
// string occurs in the first
// string, whether continuous
// or discontinuous
import java.io.*;
 
class GFG
{
     
// Iterative DP function to
// find the number of times
// the second string occurs
// in the first string, whether
// continuous or discontinuous
static int count(String a, String b)
{
    int m = a.length();
    int n = b.length();
 
    // Create a table to store
    // results of sub-problems
    int lookup[][] = new int[m + 1][n + 1];
 
    // If first string is empty
    for (int i = 0; i <= n; ++i)

РЕКОМЕНДУЕМЫЕ СТАТЬИ