Dadas dos strings S y T de longitud N y M respectivamente, la tarea es contar el número de substrings de S que contienen la string T como una substring.
Ejemplos:
Entrada: S = “dabc”, T = “ab”
Salida: 4
Explicación: Las
substrings de S que contienen T como substring son:
- S[0, 2] = “pinchazo”
- S[1, 2] = “ab”
- S[1, 3] = “abc”
- S[0, 3] = “dabc”
Entrada: S = “hshshshs” T = “hs”
Salida: 25
Enfoque ingenuo: para conocer el enfoque más simple para resolver el problema, consulte la publicación anterior de este artículo.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: para optimizar el enfoque anterior, la idea es encontrar todas las ocurrencias de T en S. Siempre que se encuentre T en S , agregue todas las substrings que contienen esta ocurrencia de T excluyendo las substrings que ya se calcularon en las ocurrencias anteriores. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos answer , para almacenar el recuento de substrings.
- Inicialice una variable, digamos last , para almacenar el índice de inicio de la última aparición de T en S .
- Iterar sobre el rango [0, N – M] usando una variable, digamos i .
- Compruebe si la substring S[i, i + M] es igual a T o no. Si se determina que es cierto, agregue (i + 1 – último) * (N – (i + M – 1)) para responder y actualice el último a (i + 1).
- De lo contrario, continúe para la siguiente iteración.
- Después de completar los pasos anteriores, imprima el valor de la respuesta como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the substrings of
// string containing another given
// string as a substring
void findOccurrences(string S, string T)
{
// Store length of string S
int n1 = S.size();
// Store length of string T
int n2 = T.size();
// Store the required count of
// substrings
int ans = 0;
// Store the starting index of
// last occurrence of T in S
int last = 0;
// Iterate in range [0, n1-n2]
for (int i = 0; i <= n1 - n2; i++) {
// Check if substring from i
// to i + n2 is equal to T
bool chk = true;
// Check if substring from i
// to i + n2 is equal to T
for (int j = 0; j < n2; j++) {
// Mark chk as false and
// break the loop
if (T[j] != S[i + j]) {
chk = false;
break;
}
}
// If chk is true
if (chk) {
// Add (i + 1 - last) *
// (n1 - (i + n2 - 1))
// to answer
ans += (i + 1 - last)
* (n1 - (i + n2 - 1));
// Update the last to i + 1
last = i + 1;
}
}
// Print the answer
cout << ans;
}
// Driver code
int main()
{
string S = "dabc", T = "ab";
// Function Call
findOccurrences(S, T);
}
Java
// Java program for the above approach
class GFG{
// Function to count the substrings of
// string containing another given
// string as a substring
static void findOccurrences(String S, String T)
{
// Store length of string S
int n1 = S.length();
// Store length of string T
int n2 = T.length();
// Store the required count of
// substrings
int ans = 0;
// Store the starting index of
// last occurrence of T in S
int last = 0;
// Iterate in range [0, n1-n2]
for (int i = 0; i <= n1 - n2; i++)
{
// Check if substring from i
// to i + n2 is equal to T
boolean chk = true;
// Check if substring from i
// to i + n2 is equal to T
for (int j = 0; j < n2; j++)
{
// Mark chk as false and
// break the loop
if (T.charAt(j) != S.charAt(i + j))
{
chk = false;
break;
}
}
// If chk is true
if (chk)
{
// Add (i + 1 - last) *
// (n1 - (i + n2 - 1))
// to answer
ans += (i + 1 - last)
* (n1 - (i + n2 - 1));
// Update the last to i + 1
last = i + 1;
}
}
// Print the answer
System.out.println(ans);
}
// Driver code
public static void main (String[] args)
{
String S = "dabc", T = "ab";
// Function Call
findOccurrences(S, T);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to count the substrings of # containing another given # as a sub def findOccurrences(S, T): # Store length of S n1 = len(S) # Store length of T n2 = len(T) # Store the required count of # substrings ans = 0 # Store the starting index of # last occurrence of T in S last = 0 # Iterate in range [0, n1-n2] for i in range(n1 - n2 + 1): # Check if subfrom i # to i + n2 is equal to T chk = True # Check if subfrom i # to i + n2 is equal to T for j in range(n2): # Mark chk as false and # break the loop if (T[j] != S[i + j]): chk = False break # If chk is true if (chk): # Add (i + 1 - last) * # (n1 - (i + n2 - 1)) # to answer ans += (i + 1 - last) * (n1 - (i + n2 - 1)) # Update the last to i + 1 last = i + 1 # Print the answer print(ans) # Driver code if __name__ == '__main__': S,T = "dabc","ab" # Function Call findOccurrences(S, T) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count the substrings of
// string containing another given
// string as a substring
static void findOccurrences(String S, String T)
{
// Store length of string S
int n1 = S.Length;
// Store length of string T
int n2 = T.Length;
// Store the required count of
// substrings
int ans = 0;
// Store the starting index of
// last occurrence of T in S
int last = 0;
// Iterate in range [0, n1-n2]
for (int i = 0; i <= n1 - n2; i++)
{
// Check if substring from i
// to i + n2 is equal to T
bool chk = true;
// Check if substring from i
// to i + n2 is equal to T
for (int j = 0; j < n2; j++)
{
// Mark chk as false and
// break the loop
if (T[j] != S[i + j])
{
chk = false;
break;
}
}
// If chk is true
if (chk)
{
// Add (i + 1 - last) *
// (n1 - (i + n2 - 1))
// to answer
ans += (i + 1 - last)
* (n1 - (i + n2 - 1));
// Update the last to i + 1
last = i + 1;
}
}
// Print the answer
Console.WriteLine(ans);
}
// Driver code
public static void Main(String[] args)
{
String S = "dabc", T = "ab";
// Function Call
findOccurrences(S, T);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for above approach
// Function to count the substrings of
// string containing another given
// string as a substring
function findOccurrences(S, T)
{
// Store length of string S
let n1 = S.length;
// Store length of string T
let n2 = T.length;
// Store the required count of
// substrings
let ans = 0;
// Store the starting index of
// last occurrence of T in S
let last = 0;
// Iterate in range [0, n1-n2]
for (let i = 0; i <= n1 - n2; i++)
{
// Check if substring from i
// to i + n2 is equal to T
let chk = true;
// Check if substring from i
// to i + n2 is equal to T
for (let j = 0; j < n2; j++)
{
// Mark chk as false and
// break the loop
if (T[j] != S[i + j])
{
chk = false;
break;
}
}
// If chk is true
if (chk)
{
// Add (i + 1 - last) *
// (n1 - (i + n2 - 1))
// to answer
ans += (i + 1 - last)
* (n1 - (i + n2 - 1));
// Update the last to i + 1
last = i + 1;
}
}
// Print the answer
document.write(ans);
}
// Driver Code
let S = "dabc", T = "ab";
// Function Call
findOccurrences(S, T);
</script>
Producción:
4
Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA