Рубрики

Количество подстрок, которые начинаются с «гиков» и заканчиваются «для»

Для заданной строки str, состоящей из строчных букв английского алфавита, задача состоит в том, чтобы найти количество подстрок, которые начинаются с «гиков» и заканчиваются на «for» .

Примеры:

Input: str = “geeksforgeeksisforgeeks”
Output: 3
“geeksfor”, “geeksforgeeksisfor” and “geeksisfor”
are the only valid substrings.

Input: str = “geeksforgeeks”
Output: 1

Наивный подход: сначала установите счетчик на 0, затем итерируйте по строке, и всякий раз, когда встречается подстрока «geeks» , из ближайших индексов снова итерируйте по строке и пытайтесь найти подстроку «for» . Если присутствует «for» , увеличьте счетчик и, наконец, напечатайте его.

Эффективный подход: установите два счетчика для подстрок «вундеркиндов» и «для» , скажем, c1 и c2. При повторении, всякий раз, когда встречается подстрока «geeks» , увеличивается c1, и всякий раз, когда встречается «for» , задайте c2 = c2 + c1 . Это связано с тем, что каждое вхождение «geeks» создает допустимую подстроку с найденным «for» . Наконец выведите c2 .

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <iostream>

using namespace std;

  
// Функция для возврата счета
// из необходимых подстрок

int countSubStr(string s, int n)

{

    int c1 = 0, c2 = 0;

  

    // Для каждого индекса строки

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

  

        // Если подстрока начинается с

        // текущий индекс "гики"

        if (s.substr(i, 5) == "geeks")

            c1++;

  

        // Если подстрока "for"

        if (s.substr(i, 3) == "for")

            c2 = c2 + c1;

    }

  

    return c2;

}

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

int main()

{

    string s = "geeksforgeeksisforgeeks";

    int n = s.size();

  

    cout << countSubStr(s, n);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG 

{

  

    // Функция для возврата счета

    // из необходимых подстрок

    static int countSubStr(String s, int n)

    {

        int c1 = 0, c2 = 0;

  

        // Для каждого индекса строки

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

        {

  

            // Если подстрока начинается с

            // текущий индекс "гики"

            if (i < n - 5 && 

                "geeks".equals(s.substring(i, i + 5))) 

            {

                c1++;

            }

  

            // Если подстрока "for"

            if (i < n - 3 && 

                "for".equals(s.substring(i, i + 3))) 

            {

                c2 = c2 + c1;

            }

        }

        return c2;

    }

  

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

    public static void main(String[] args)

    {

        String s = "geeksforgeeksisforgeeks";

        int n = s.length();

        System.out.println(countSubStr(s, n));

    }

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

python3

# Python3 реализация подхода

  
# Функция для возврата счета
Количество обязательных подстрок

def countSubStr(s, n) : 

  

    c1 = 0; c2 = 0

  

    # Для каждого индекса строки

    for i in range(n) :

  

        # Если подстрока начинается с

        # текущий индекс "гики"

        if (s[i : i + 5] == "geeks") :

            c1 += 1

  

        # Если подстрока "для"

        if (s[i :i+ 3] == "for") :

            c2 = c2 + c1; 

  

    return c2; 

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

if __name__ == "__main__"

  

    s = "geeksforgeeksisforgeeks"

    n = len(s); 

  

    print(countSubStr(s, n)); 

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

C #

// C # реализация подхода

using System;

      

public class GFG 

{

   

    // Функция для возврата счета

    // из необходимых подстрок

    static int countSubStr(String s, int n)

    {

        int c1 = 0, c2 = 0;

   

        // Для каждого индекса строки

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

        {

   

            // Если подстрока начинается с

            // текущий индекс "гики"

            if (i < n - 5 && 

                "geeks".Equals(s.Substring(i, 5))) 

            {

                c1++;

            }

   

            // Если подстрока "for"

            if (i < n - 3 && 

                "for".Equals(s.Substring(i, 3))) 

            {

                c2 = c2 + c1;

            }

        }

        return c2;

    }

   

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

    public static void Main(String[] args)

    {

        String s = "geeksforgeeksisforgeeks";

        int n = s.Length;

        Console.WriteLine(countSubStr(s, n));

    }

}

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

Выход:

3

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

Количество подстрок, которые начинаются с «гиков» и заканчиваются «для»

0.00 (0%) 0 votes