Compruebe si la string dada es K-periódica para todos los K en el rango [1, N]

Dada una string str de tamaño N , la tarea es verificar si la string dada es K-periódica , para todas las K en el rango [1, N] . Imprima Sí si la string dada es K-periódica , de lo contrario imprima No.

Una string es K-periódica , si la string es una repetición de la substring str[0 … k-1].

Por ejemplo, la string «ababab» es 2-periódica. 

Ejemplos:

Entrada: N = 7, S = “abcabca”
Salida: 3 6 7
Explicación: 
1. Considere el prefijo de longitud 1 (es decir, “a”), luego, si repetimos este prefijo para hacer una string de longitud 7, obtenemos “aaaaaaa ” que no es igual a la string original.
2. Considere el prefijo de longitud 2 (es decir, «ab»), luego, si repetimos este prefijo para hacer una string de longitud 7, obtenemos «abababa», que no es igual a la string original.
3. Considere el prefijo de longitud 3 (es decir, «abc»), luego, si repetimos este prefijo para hacer una string de longitud 7, obtenemos «abcabca», que es igual a la string original.
4. Considere el prefijo de longitud 4 (es decir, «abca»), luego, si repetimos este prefijo para hacer una string de longitud 7, obtenemos «abcaabc», que no es igual a la string original.
5. Considere el prefijo de longitud 5 (es decir, «abcab»), luego, si repetimos este prefijo para hacer una string de longitud 7, obtenemos «abcabab», que no es igual a la string original.
6. Considere el prefijo de longitud 6 (es decir, «abcabc»), luego, si repetimos este prefijo para hacer una string de longitud 7, obtenemos «abcabca», que es igual a la string original.
7. Considere el prefijo de longitud 7 (es decir, «abcabca»), luego, si repetimos este prefijo para hacer una string de longitud 7, obtenemos «abcabca», que es igual a la string original.

Entrada: N = 5, S = “aaaa”
Salida: 1 2 3 4 5
Explicación:   Como todos los caracteres de la string dada son iguales, la string se puede generar repitiendo el prefijo de longitud 1 a N.

Enfoque: La tarea se puede resolver usando el algoritmo z .

• Construyamos una array Z para la string dada. (0-indexado)
• Entonces, para que i sea un período, (Ni) debe ser igual al valor z en el índice i, porque si ‘i’ es uno de los períodos de la string, entonces un sufijo de longitud (Ni) coincide exactamente con el prefijo de longitud (ni).
• Por último, agregue N (longitud de la string) a la respuesta, el valor de N es trivial y el método mencionado anteriormente no lo encuentra.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach:
#include <iostream>
using namespace std;
 
void getZarr(string str, int Z[]);
 
// Prints all the period of a string
void findPeriod(string text)
{
    int l = text.length();
 
    // Construct Z array
    int Z[l];
    getZarr(text, Z);
 
    // Now looping through Z array
    // For finding period
    for (int i = 1; i < l; ++i) {
 
        // If(l-i) is equal to Z[i],
        // Then one of the period
        // Of string is i
        if (Z[i] == (l - i))
            cout << i << " ";
    }
 
    // Print trivial value
    //(i.e. length of string)
    cout << l << endl;
}
 
// Fills Z array for given string str[]
void getZarr(string str, int Z[])
{
    int n = str.length();
    int L, R, k;
 
    // [L, R] make a window
    // Which matches with prefix of s
    L = R = 0;
    for (int i = 1; i < n; ++i) {
        // If i>R nothing matches
        // So we will calculate.
        // Z[i] using naive way.
        if (i > R) {
            L = R = i;
 
            // R-L = 0 in starting, so it will start
            // Checking from 0'th index. For example,
            // For "ababab" and i = 1, the value of R
            // Remains 0 and Z[i] becomes 0. For string
            // "aaaaaa" and i = 1, Z[i] and R become 5
            while (R < n && str[R - L] == str[R])
                R++;
            Z[i] = R - L;
            R--;
        }
        else {
            // k = i-L so k corresponds to number
            // Which matches in [L, R] interval.
            k = i - L;
 
            // If Z[k] is less than remaining interval
            // Then Z[i] will be equal to Z[k].
            // For example, str = "ababab", i = 3, R = 5
            // and L = 2
            if (Z[k] < R - i + 1)
                Z[i] = Z[k];
 
            // For example str = "aaaaaa"
            // and i = 2, R is 5, L is 0
            else {
 
                // Else start from R
                // And check manually
                L = i;
                while (R < n && str[R - L] == str[R])
                    R++;
                Z[i] = R - L;
                R--;
            }
        }
    }
}
 
// Driver code
int main()
{
    string text = "abcabca";
    findPeriod(text);
    return 0;
}

// A Java program that implements Z algorithm for period
// finding
class GFG {
 
    // prints all the period of string
    public static void findPeriod(String text)
    {
 
        int l = text.length();
 
        int Z[] = new int[l];
 
        // Construct Z array
        getZarr(text, Z);
 
        // now looping through Z array for finding period
        for (int i = 0; i < l; ++i) {
 
            // if Z[i] is equal to (l-i), then one
            // of the period of string is i
 
            if (Z[i] == (l - i)) {
                System.out.print(i + " ");
            }
        }
 
        // Print trivial value (i.e. length of string)
        System.out.println(l);
    }
 
    // Fills Z array for given string str[]
    private static void getZarr(String str, int[] Z)
    {
 
        int n = str.length();
 
        // [L, R] make a window which matches with
        // prefix of s
        int L = 0, R = 0;
 
        for (int i = 1; i < n; ++i) {
 
            // if i>R nothing matches so we will calculate.
            // Z[i] using naive way.
            if (i > R) {
 
                L = R = i;
 
                // R-L = 0 in starting, so it will start
                // checking from 0'th index. For example,
                // for "ababab" and i = 1, the value of R
                // remains 0 and Z[i] becomes 0. For string
                // "aaaaaa" and i = 1, Z[i] and R become 5
 
                while (R < n && str.charAt(R - L) == str.charAt(R))
                    R++;
 
                Z[i] = R - L;
                R--;
            }
            else {
 
                // k = i-L so k corresponds to number which
                // matches in [L, R] interval.
                int k = i - L;
 
                // if Z[k] is less than remaining interval
                // then Z[i] will be equal to Z[k].
                // For example, str = "ababab", i = 3, R = 5
                // and L = 2
                if (Z[k] < R - i + 1)
                    Z[i] = Z[k];
 
                // For example str = "aaaaaa" and i = 2, R is 5,
                // L is 0
                else {
 
                    // else start from R and check manually
                    L = i;
                    while (R < n && str.charAt(R - L) == str.charAt(R))
                        R++;
 
                    Z[i] = R - L;
                    R--;
                }
            }
        }
    }
 
    // Driver program
    public static void main(String[] args)
    {
        String text = "abcabca";
 
        findPeriod(text);
    }
}

# python3 code for the above approach:
 
# Fills Z array for given string str[]
def getZarr(str, Z):
 
    n = len(str)
    L, R, k = 0, 0, 0
 
    # [L, R] make a window
    # Which matches with prefix of s
 
    for i in range(1, n):
        # If i>R nothing matches
        # So we will calculate.
        # Z[i] using naive way.
        if (i > R):
            L = R = i
 
            # R-L = 0 in starting, so it will start
            # Checking from 0'th index. For example,
            # For "ababab" and i = 1, the value of R
            # Remains 0 and Z[i] becomes 0. For string
            # "aaaaaa" and i = 1, Z[i] and R become 5
            while (R < n and str[R - L] == str[R]):
                R += 1
            Z[i] = R - L
            R -= 1
 
        else:
            # k = i-L so k corresponds to number
            # Which matches in [L, R] interval.
            k = i - L
 
            # If Z[k] is less than remaining interval
            # Then Z[i] will be equal to Z[k].
            # For example, str = "ababab", i = 3, R = 5
            # and L = 2
            if (Z[k] < R - i + 1):
                Z[i] = Z[k]
 
            # For example str = "aaaaaa"
            # and i = 2, R is 5, L is 0
            else:
 
                # Else start from R
                # And check manually
                L = i
                while (R < n and str[R - L] == str[R]):
                    R += 1
                Z[i] = R - L
                R -= 1
 
 
# Prints all the period of a string
def findPeriod(text):
 
    l = len(text)
 
    # Construct Z array
    Z = [0 for _ in range(l)]
    getZarr(text, Z)
 
    # Now looping through Z array
    # For finding period
    for i in range(1, l):
 
        # If(l-i) is equal to Z[i],
        # Then one of the period
        # Of string is i
        if (Z[i] == (l - i)):
            print(i, end=" ")
 
    # Print trivial value
    # (i.e. length of string)
    print(l)
 
# Driver code
if __name__ == "__main__":
 
    text = "abcabca"
    findPeriod(text)
 
# This code is contributed by rakeshsahni

// C# code for the above approach:
using System;
class GFG {
 
  // Prints all the period of a string
  static void findPeriod(string text)
  {
    int l = text.Length;
 
    // Construct Z array
    int[] Z = new int[l];
    getZarr(text, Z);
 
    // Now looping through Z array
    // For finding period
    for (int i = 1; i < l; ++i) {
 
      // If(l-i) is equal to Z[i],
      // Then one of the period
      // Of string is i
      if (Z[i] == (l - i))
        Console.Write(i + " ");
    }
 
    // Print trivial value
    //(i.e. length of string)
    Console.WriteLine(l);
  }
 
  // Fills Z array for given string str[]
  static void getZarr(string str, int[] Z)
  {
    int n = str.Length;
    int L, R, k;
 
    // [L, R] make a window
    // Which matches with prefix of s
    L = R = 0;
    for (int i = 1; i < n; ++i) {
      // If i>R nothing matches
      // So we will calculate.
      // Z[i] using naive way.
      if (i > R) {
        L = R = i;
 
        // R-L = 0 in starting, so it will start
        // Checking from 0'th index. For example,
        // For "ababab" and i = 1, the value of R
        // Remains 0 and Z[i] becomes 0. For string
        // "aaaaaa" and i = 1, Z[i] and R become 5
        while (R < n && str[R - L] == str[R])
          R++;
        Z[i] = R - L;
        R--;
      }
      else {
        // k = i-L so k corresponds to number
        // Which matches in [L, R] interval.
        k = i - L;
 
        // If Z[k] is less than remaining interval
        // Then Z[i] will be equal to Z[k].
        // For example, str = "ababab", i = 3, R = 5
        // and L = 2
        if (Z[k] < R - i + 1)
          Z[i] = Z[k];
 
        // For example str = "aaaaaa"
        // and i = 2, R is 5, L is 0
        else {
 
          // Else start from R
          // And check manually
          L = i;
          while (R < n && str[R - L] == str[R])
            R++;
          Z[i] = R - L;
          R--;
        }
      }
    }
  }
 
  // Driver code
  public static int Main()
  {
    string text = "abcabca";
    findPeriod(text);
    return 0;
  }
}
 
// This code is contributed by Taranpreet

<script>
       // JavaScript code for the above approach
// Fills Z array for given string str[]
function getZarr(str,  Z)
{
    let n = str.length;
    let L, R, k;
 
    // [L, R] make a window
    // Which matches with prefix of s
    L = R = 0;
    for (let i = 1; i < n; ++i) {
        // If i>R nothing matches
        // So we will calculate.
        // Z[i] using naive way.
        if (i > R) {
            L = R = i;
 
            // R-L = 0 in starting, so it will start
            // Checking from 0'th index. For example,
            // For "ababab" and i = 1, the value of R
            // Remains 0 and Z[i] becomes 0. For string
            // "aaaaaa" and i = 1, Z[i] and R become 5
            while (R < n && str[R - L] == str[R])
                R++;
            Z[i] = R - L;
            R--;
        }
        else {
            // k = i-L so k corresponds to number
            // Which matches in [L, R] interval.
            k = i - L;
 
            // If Z[k] is less than remaining interval
            // Then Z[i] will be equal to Z[k].
            // For example, str = "ababab", i = 3, R = 5
            // and L = 2
            if (Z[k] < R - i + 1)
                Z[i] = Z[k];
 
            // For example str = "aaaaaa"
            // and i = 2, R is 5, L is 0
            else {
 
                // Else start from R
                // And check manually
                L = i;
                while (R < n && str[R - L] == str[R])
                    R++;
                Z[i] = R - L;
                R--;
            }
        }
    }
}
 
// Prints all the period of a string
function findPeriod(text)
{
    let l = text.length;
 
    // Construct Z array
    let Z= new Array(l);
    getZarr(text, Z);
 
    // Now looping through Z array
    // For finding period
    for (let i = 1; i < l; ++i) {
 
        // If(l-i) is equal to Z[i],
        // Then one of the period
        // Of string is i
        if (Z[i] == (l - i))
            document.write(i + " ")
    }
 
    // Print trivial value
    //(i.e. length of string)
    document.write(l + '<br>')
}
 
// Driver code
 
    let text = "abcabca";
    findPeriod(text);
    
     // This code is contributed by Potta Lokesh
    </script>

3 6 7

Complejidad temporal: O(N)
Espacio auxiliar: O(N)