Рубрики

Запросы на частоты символов в подстроках

Дана строка s и Q количество запросов. Каждый запрос Q состоит из l и r и символа c. Найти частоту символа c в подстроке с l по r.

Примеры:

Input : s = geeksforgeeks
        4
        0 5 e
        2 6 f
        4 7 m
        0 12 e
Output : 2
         1
         0
         4
Substring from 0 to 5 is geeksf.
Here e occurs 2 times.

Input : s = apple
        2
        0 4 e
        1 2 p        
Output : 1
         2 

Наивный подход: запустить цикл от l до r для Q количества запросов. Посчитайте вхождение символа и количество возвратов. Общая сложность по времени будет Q * O (| s |).

Эффективный подход: мы можем предварительно рассчитать количество для каждого символа. Хранить количество каждого символа в двумерном массиве. Возвращаемая частота символа от 0 до r минус частота символа в диапазоне от 0 до l в O (1). Общая сложность по времени будет Q * O (1).

C ++

// Программа CPP для поиска вхождения
// символа в подстроке от l до r
#include <bits/stdc++.h>
#define MAX_LEN 1005
#define MAX_CHAR 26

  

using namespace std;

  
// Хранить количество всех символов

int cnt[MAX_LEN][MAX_CHAR];

  
// Для предварительной обработки строки из
// 0 к размеру строки

void preProcess(string s)

{

    int n = s.length();

  

    // Инициализация cnt с 0

    memset(cnt, 0, sizeof(cnt));

  

    // Сохранить вхождение

    // персонаж я

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

        cnt[i][s[i] - 'a']++;

  

    // Сохранение вхождения o

    // все персонажи до меня

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

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

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

    }

}

  
// Вернуть вхождение
// символ в диапазоне от l до r

int findCharFreq(int l, int r, char c)

{

    // Возвращаем вхождение символа

    // от 0 до r минус

    // вхождение от 0 до l

    return cnt[r] - cnt[l - 1];

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    string s = "geeksforgeeks";

    int Q = 4;

    preProcess(s);

  

    cout << findCharFreq(0, 5, 'e') << endl;

    cout << findCharFreq(2, 6, 'f') << endl;

    cout << findCharFreq(4, 7, 'm') << endl;

    cout << findCharFreq(0, 12, 'e') << endl;

  

    return 0;

}

Джава

// Java-программа для поиска вхождения
// символа в подстроке от l до r

import java.util.*;

  

class GFG

{

  

static int MAX_LEN = 1005;

static int MAX_CHAR = 26;

  
// Хранить количество всех символов

static int [][]cnt = new int[MAX_LEN][MAX_CHAR];

  
// Для предварительной обработки строки из
// 0 к размеру строки

static void preProcess(String s)

{

    int n = s.length();

  

    // Сохранить вхождение

    // персонаж я

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

        cnt[i][s.charAt(i) - 'a']++;

  

    // Сохранение вхождения o

    // все персонажи до меня

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

    {

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

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

    }

}

  
// Вернуть вхождение
// символ в диапазоне от l до r

static int findCharFreq(int l, int r, char c)

{

    // Возвращаем вхождение символа

    // от 0 до r минус

    // вхождение от 0 до l

    return (cnt[r][(c) - 97] - cnt[l][(c) - 97]);

}

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

public static void main(String[] args) 

{

    String s = "geeksforgeeks";

    int Q = 4;

    preProcess(s);

  

    System.out.println(findCharFreq(0, 5, 'e'));

    System.out.println(findCharFreq(2, 6, 'f'));

    System.out.println(findCharFreq(4, 7, 'm'));

    System.out.println(findCharFreq(0, 12, 'e'));

}

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

python3

# Python3 программа для поиска вхождения
Количество символов в подстроке от l до r

MAX_LEN, MAX_CHAR = 1005, 26

  
# Хранить количество всех символов

cnt = [[0 for i in range(MAX_CHAR)] 

          for j in range(MAX_LEN)] 

  
# Для предварительной обработки строки из
# 0 к размеру строки

def preProcess(s): 

  

    n = len(s) 

  

    # Хранить вхождение символа i

    for i in range(0, n): 

        cnt[i][ord(s[i]) - ord('a')] += 1

  

    # Сохранение вхождения o

    # все персонажи до меня

    for i in range(0, n): 

        for j in range(0, 26): 

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

      
# Вернуть вхождение
# символ в диапазоне от l до r

def findCharFreq(l, r, c): 

  

    # Вернуть вхождение символа

    # от 0 до г минус его

    # вхождение от 0 до l

    return (cnt[r][ord(c) - 97] - 

            cnt[l - 1][ord(c) - 97]) 

  
Код водителя

if __name__ == "__main__"

  

    s = "geeksforgeeks"

    Q = 4

    preProcess(s) 

  

    print(findCharFreq(0, 5, 'e')) 

    print(findCharFreq(2, 6, 'f')) 

    print(findCharFreq(4, 7, 'm')) 

    print(findCharFreq(0, 12, 'e')) 

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

C #

// C # программа для поиска вхождения
// символа в подстроке от l до r

using System;

  

class GFG

{

    static int MAX_LEN = 1005;

    static int MAX_CHAR = 26;

  

    // Хранить количество всех символов

    static int[,] cnt = new int[MAX_LEN, 

                                MAX_CHAR];

  

    // Для предварительной обработки строки из

    // 0 к размеру строки

    static void preProcess(string s)

    {

        int n = s.Length;

  

        // Сохранить вхождение

        // персонаж я

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

            cnt[i, s[i] - 'a']++;

  

        // Сохранение вхождения o

        // все персонажи до меня

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

        {

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

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

        }

    }

  

    // Вернуть вхождение

    // символ в диапазоне от l до r

    static int findCharFreq(int l, int r, char c)

    {

        // Возвращаем вхождение символа

        // от 0 до r минус

        // вхождение от 0 до l

        return (cnt[r, c - 97] - cnt[l, c - 97]);

    }

  

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

    public static void Main(string[] args)

    {

        string s = "geeksforgeeks";

        int Q = 4;

        preProcess(s);

  

        Console.WriteLine(findCharFreq(0, 5, 'e'));

        Console.WriteLine(findCharFreq(2, 6, 'f'));

        Console.WriteLine(findCharFreq(4, 7, 'm'));

        Console.WriteLine(findCharFreq(0, 12, 'e'));

    }

}

  
// Этот код поддерживается
// sanjeev2552



Выход:

2
1
0
4

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

Запросы на частоты символов в подстроках

0.00 (0%) 0 votes