Dadas tres strings S , S1 y S2 , la tarea es verificar si la cantidad de substrings que comienzan y terminan con S1 y S2 es igual a la cantidad de substrings que comienzan y terminan con S2 y S1 o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: S = “holamundomundoholamundo”, S1 = “hola”, S2 = “mundo”
Salida: No
Explicación:
Las substrings que comienzan con S1 (= “hola”) y terminan con S2 (= “mundo”) son {“holamundo ”, “holamundomundo”, “holamundomundoholamundo”, “holamundo”}.
Por lo tanto, el recuento total es 4.
Las substrings que comienzan con S2 (= “mundo”) y terminan con S1(= “hola”) son {“mundomundohola”, “mundohola”}.
Por lo tanto, el conteo total es 2.
Por lo tanto, los dos conteos anteriores no son iguales.Entrada: S = «abrircerrarabrircerrarabrir», S1 = «abrir», S2 = «cerrar»
Salida: Sí
Enfoque: siga los pasos a continuación para resolver el problema:
- Almacene la longitud de las strings S , S1 y S2 en variables, digamos N , N1 y N2 respectivamente.
- Inicialice una variable, digamos count , para almacenar el número de ocurrencias de la substring S1 en la string S .
- Inicialice una variable, digamos ans , para almacenar substrings que comiencen y terminen con S1 y S2 respectivamente.
- Atraviese la string S dada y realice los siguientes pasos:
- Almacene la substring de la string S que comienza en el índice i de tamaño N1 en el prefijo de string .
- Almacene la substring de la string S que comienza en el índice i de tamaño N2 en el sufijo de string .
- Si el prefijo es el mismo que el de la string S1 , incremente el valor de count en 1 .
- Si el sufijo es el mismo que la string S2 , incremente el valor de ans por conteo .
- Use los pasos anteriores para encontrar la cantidad de substrings que comienzan y terminan con S2 y S1 respectivamente. Almacene el conteo obtenido en la variable digamos ans2 .
- Si se encuentra que los valores de ans y ans2 son iguales, imprima «Sí» . De lo contrario, escriba “No” .
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 number of // substrings that starts with // string S1 and ends with string S2 int countSubstrings(string S, string S1, string S2) { // Stores the length of each string int N = S.length(); int N1 = S1.length(); int N2 = S2.length(); // Stores the count of prefixes // as S1 and suffixes as S2 int count = 0, totalcount = 0; // Traverse string S for (int i = 0; i < N; i++) { // Find the prefix at index i string prefix = S.substr(i, N1); // Find the suffix at index i string suffix = S.substr(i, N2); // If the prefix is S1 if (S1 == prefix) count++; // If the suffix is S2 if (S2 == suffix) totalcount += count; } // Return the count of substrings return totalcount; } // Function to check if the number of // substrings starts with S1 and ends // with S2 and vice-versa is same or not void checkSubstrings(string S, string S1, string S2) { // Count the number of substrings int x = countSubstrings(S, S1, S2); int y = countSubstrings(S, S2, S1); // Print the result if (x == y) cout << "Yes"; else cout << "No"; } // Driver Code int main() { string S = "opencloseopencloseopen"; string S1 = "open"; string S2 = "close"; checkSubstrings(S, S1, S2); return 0; }
Java
// Java program for the above approach class GFG{ // Function to count number of // substrings that starts with // string S1 and ends with string S2 static int countSubstrings(String S, String S1, String S2) { // Stores the length of each string int N = S.length(); int N1 = S1.length(); int N2 = S2.length(); // Stores the count of prefixes // as S1 and suffixes as S2 int count = 0, totalcount = 0; // Traverse string S for(int i = 0; i < N; i++) { // Find the prefix at index i String prefix = S.substring( i, (i + N1 < N) ? (i + N1) : N); // Find the suffix at index i String suffix = S.substring( i, (i + N2 < N) ? (i + N2) : N); // If the prefix is S1 if (S1.equals(prefix)) count++; // If the suffix is S2 if (S2.equals(suffix)) totalcount += count; } // Return the count of substrings return totalcount; } // Function to check if the number of // substrings starts with S1 and ends // with S2 and vice-versa is same or not static void checkSubstrings(String S, String S1, String S2) { // Count the number of substrings int x = countSubstrings(S, S1, S2); int y = countSubstrings(S, S2, S1); // Print the result if (x == y) System.out.println("Yes"); else System.out.println("No"); } // Driver Code public static void main(String[] args) { String S = "opencloseopencloseopen"; String S1 = "open"; String S2 = "close"; checkSubstrings(S, S1, S2); } } // This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach # Function to count number of # substrings that starts with # string S1 and ends with string S2 def countSubstrings(S, S1, S2): # Stores the length of each string N = len(S) N1 = len(S1) N2 = len(S2) # Stores the count of prefixes # as S1 and suffixes as S2 count = 0 totalcount = 0 # Traverse string S for i in range(N): # Find the prefix at index i prefix = S[i: (i + N1) if (i + N1 < N) else N] # Find the suffix at index i suffix = S[i: (i + N2) if (i + N2 < N) else N] # If the prefix is S1 if S1 == prefix: count += 1 # If the suffix is S2 if S2 == suffix: totalcount += count # Return the count of substrings return totalcount # Function to check if the number of # substrings starts with S1 and ends # with S2 and vice-versa is same or not def checkSubstrings(S, S1, S2): x = countSubstrings(S, S1, S2) y = countSubstrings(S, S2, S1) if x == y: print("Yes") else: print("No") # Driver code S = "opencloseopencloseopen" S1 = "open" S2 = "close" checkSubstrings(S, S1, S2) # This code is contributed by abhinavjain194
C#
// C# program for the above approach using System; class GFG{ // Function to count number of // substrings that starts with // string S1 and ends with string S2 static int countSubstrings(string S, string S1, string S2) { // Stores the length of each string int N = S.Length; int N1 = S1.Length; int N2 = S2.Length; // Stores the count of prefixes // as S1 and suffixes as S2 int count = 0, totalcount = 0; // Traverse string S for(int i = 0; i < N; i++) { // Find the prefix at index i String prefix = S.Substring( i, (i + N1 < N) ? N1 : (N - i)); // Find the suffix at index i String suffix = S.Substring( i, (i + N2 < N) ? N2 : (N - i)); // If the prefix is S1 if (S1.Equals(prefix)) count++; // If the suffix is S2 if (S2.Equals(suffix)) totalcount += count; } // Return the count of substrings return totalcount; } // Function to check if the number of // substrings starts with S1 and ends // with S2 and vice-versa is same or not static void checkSubstrings(string S, string S1, string S2) { // Count the number of substrings int x = countSubstrings(S, S1, S2); int y = countSubstrings(S, S2, S1); // Print the result if (x == y) Console.Write("Yes"); else Console.Write("No"); } // Driver code static void Main() { string S = "opencloseopencloseopen"; string S1 = "open"; string S2 = "close"; checkSubstrings(S, S1, S2); } } // This code is contributed by abhinavjain194
Javascript
<script> // Javascript program for the above approach // Function to count number of // substrings that starts with // string S1 and ends with string S2 function countSubstrings(S, S1, S2) { // Stores the length of each string let N = S.length; let N1 = S1.length; let N2 = S2.length; // Stores the count of prefixes // as S1 and suffixes as S2 let count = 0, totalcount = 0; // Traverse string S for (let i = 0; i < N; i++) { // Find the prefix at index i let prefix = S.substr(i, N1); // Find the suffix at index i let suffix = S.substr(i, N2); // If the prefix is S1 if (S1 == prefix) count++; // If the suffix is S2 if (S2 == suffix) totalcount += count; } // Return the count of substrings return totalcount; } // Function to check if the number of // substrings starts with S1 and ends // with S2 and vice-versa is same or not function checkSubstrings(S, S1, S2) { // Count the number of substrings let x = countSubstrings(S, S1, S2); let y = countSubstrings(S, S2, S1); // Print the result if (x == y) document.write("Yes"); else document.write("No"); } // Driver Code let S = "opencloseopencloseopen"; let S1 = "open"; let S2 = "close"; checkSubstrings(S, S1, S2); // This code is contributed by gfgking </script>
Yes
Complejidad de tiempo: O(N * (N1 + N2)), donde N, N1 y N2 son la longitud de las strings S, S1 y S2 respectivamente.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por varunkedia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA