Longitud de todos los prefijos que también son los sufijos de la string dada

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:

1. “ab” de longitud = 2
2. “abab” de longitud = 4
3. “ababab” de longitud = 6
4. “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++ 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 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 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# 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.

<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 ² )
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++ 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)