Dada una string S que consta de N caracteres, la tarea es encontrar la longitud de todos los prefijos de la string S dada que también son sufijos de la misma string S.
Ejemplos:
Entrada: S = “ababababab”
Salida: 2 4 6 8
Explicación:
Los prefijos de S que también son sus sufijos son:
- “ab” de longitud = 2
- “abab” de longitud = 4
- “ababab” de longitud = 6
- “abababab” de longitud = 8
Entrada: S = «geeksforgeeks»
Salida: 5
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es atravesar la string dada , S desde el principio, y en cada iteración agregar el carácter actual a la string de prefijo, y verificar si la string de prefijo es la misma que el sufijo de la misma longitud o no . Si se encuentra que es verdadero , imprima la longitud de la string de prefijo. De lo contrario, busque el siguiente prefijo.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the length of all // prefixes of the given string that // are also suffixes of the same string void countSamePrefixSuffix(string s, int n) { // Stores the prefix string string prefix = ""; // Traverse the string S for (int i = 0; i < n - 1; i++) { // Add the current character // to the prefix string prefix += s[i]; // Store the suffix string string suffix = s.substr( n - 1 - i, n - 1); // Check if both the strings // are equal or not if (prefix == suffix) { cout << prefix.size() << " "; } } } // Driver Code int main() { string S = "ababababab"; int N = S.size(); countSamePrefixSuffix(S, N); return 0; }
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Function to find the length of all // prefixes of the given string that // are also suffixes of the same string static void countSamePrefixSuffix(String s, int n) { // Stores the prefix string String prefix = ""; // Traverse the string S for(int i = 0; i < n - 1; i++) { // Add the current character // to the prefix string prefix += s.charAt(i); // Store the suffix string String suffix = s.substring(n - 1 - i, n); // Check if both the strings // are equal or not if (prefix.equals(suffix)) { System.out.print(prefix.length() + " "); } } } // Driver Code public static void main(String[] args) { String S = "ababababab"; int N = S.length(); countSamePrefixSuffix(S, N); } } // This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function to find the length of all # prefixes of the given that # are also suffixes of the same string def countSamePrefixSuffix(s, n): # Stores the prefix string prefix = "" # Traverse the S for i in range(n - 1): # Add the current character # to the prefix string prefix += s[i] # Store the suffix string suffix = s[n - 1 - i: 2 * n - 2 - i] # Check if both the strings # are equal or not if (prefix == suffix): print(len(prefix), end = " ") # Driver Code if __name__ == '__main__': S = "ababababab" N = len(S) countSamePrefixSuffix(S, N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the length of all // prefixes of the given string that // are also suffixes of the same string static void countSamePrefixSuffix(string s, int n) { // Stores the prefix string string prefix = ""; // Traverse the string S for (int i = 0; i < n - 1; i++) { // Add the current character // to the prefix string prefix += s[i]; // Store the suffix string string suffix = s.Substring(n - 1 - i, i+1); // Check if both the strings // are equal or not if (prefix == suffix) { Console.Write(prefix.Length + " "); } } } // Driver Code public static void Main() { string S = "ababababab"; int N = S.Length; countSamePrefixSuffix(S, N); } } // This code is contributed by SURENDRA_GANGWAR.
Javascript
<script> // JavaScript program for the above approach // Function to find the length of all // prefixes of the given string that // are also suffixes of the same string function countSamePrefixSuffix( s, n) { // Stores the prefix string var prefix = ""; // Traverse the string S for(let i = 0; i < n - 1; i++) { // Add the current character // to the prefix string prefix += s.charAt(i); // Store the suffix string var suffix = s.substring(n - 1 - i, n); // Check if both the strings // are equal or not if (prefix==suffix) { document.write(prefix.length + " "); } } } // Driver Code let S = "ababababab"; let N = S.length; countSamePrefixSuffix(S, N); </script>
2 4 6 8
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de hashing para almacenar los prefijos de la string dada. Luego, recorre todos los sufijos y verifica si están presentes en el mapa hash o no. Siga los pasos a continuación para resolver el problema:
- Inicialice dos deques , diga prefijo y sufijo para almacenar la string de prefijo y las strings de sufijo de S.
- Inicialice un HashMap , diga M para almacenar todos los prefijos de S.
- Atraviese la string dada S sobre el rango [0, N – 2] usando la variable i
- Empuje el carácter actual en la parte posterior del prefijo y el sufijo deque.
- Marque el prefijo como verdadero en HashMap M .
- Después del ciclo, agregue el último carácter de la string, diga S[N – 1] al sufijo .
- Iterar sobre el rango [0, N – 2] y realizar los siguientes pasos:
- Elimine el carácter frontal del sufijo .
- Ahora, verifique si el deque actual está presente en el HashMap M o no. Si se encuentra que es cierto , imprima el tamaño de la deque .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the length of all // prefixes of the given string that // are also suffixes of the same string void countSamePrefixSuffix(string s, int n) { // Stores the prefixes of the string map<deque<char>, int> cnt; // Stores the prefix & suffix strings deque<char> prefix, suffix; // Iterate in the range [0, n - 2] for (int i = 0; i < n - 1; i++) { // Add the current character to // the prefix and suffix strings prefix.push_back(s[i]); suffix.push_back(s[i]); // Mark the prefix as 1 in // the HashMap cnt[prefix] = 1; } // Add the last character to // the suffix suffix.push_back(s[n - 1]); int index = n - 1; // Iterate in the range [0, n - 2] for (int i = 0; i < n - 1; i++) { // Remove the character from // the front of suffix deque // to get the suffix string suffix.pop_front(); // Check if the suffix is // present in HashMap or not if (cnt[suffix] == 1) { cout << index << " "; } index--; } } // Driver Code int main() { string S = "ababababab"; int N = S.size(); countSamePrefixSuffix(S, N); return 0; }
8 6 4 2
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Stream_Cipher y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA