Conteo de ocurrencias de cada prefijo en una string usando el algoritmo KMP modificado

Dada una string S de tamaño N , la tarea es contar las ocurrencias de todos los prefijos de la string S dada .

Ejemplos:  

Entrada: S = “AAAA” 
Salida: 
A ocurre 4 veces 
AA ocurre 3 veces. 
AAA ocurre 2 veces. 
AAAA ocurre 1 veces. 
Explicación: 
A continuación se muestra la ilustración de todos los prefijos: 
 

Entrada: S = “ABACABA” 
Salida: 
A ocurre 4 veces 
AB ocurre 2 veces 
ABA ocurre 2 veces 
ABAC ocurre 1 vez 
ABACA ocurre 1 vez 
ABACAB ocurre 1 vez 
ABACABA ocurre 1 vez 
 

Enfoque ingenuo:  

1. Recorra todos los prefijos del conjunto P. Sea la x el prefijo.
2. Haga un enfoque de ventana deslizante de tamaño |x|.
3. Compruebe si la ventana deslizante actual en S es igual a x. En caso afirmativo, aumente la cuenta [x] en 1.

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

Enfoque eficiente: 
use la array LPS (también llamada prefix_function ) del algoritmo KMP . 
La función de prefijo para esta string se define como una array LPS de longitud N , donde LPS[i] es la longitud del prefijo propio más largo de la substring S[0…i], que también es un sufijo de esta substring. Sea occ[i] el número de ocurrencias del prefijo de longitud i .

A continuación se detallan los pasos para implementar este enfoque:  

1. Calcule la array LPS o prefix_function .
2. Para cada valor de la función de prefijo, primero, cuente cuántas veces ocurre en la array LPS .
3. El prefijo de longitud i aparece exactamente ans[i] veces, entonces este número debe sumarse al número de ocurrencias de su sufijo más largo que también es un prefijo.
4. Al final, agregue 1 a todos los valores de la array occ , debido al prefijo original que también debe contarse.

Por ejemplo: 
LPS[i] denota que en la posición i aparece un prefijo de longitud = LPS[i] . Y este es el prefijo más largo posible. Pero pueden ocurrir prefijos más cortos. 
Para String S = “AAAA” , los siguientes son los prefijos: 
 

S[0..0] = A 
S[0..1] = AA 
S[0..2] = AAA 
S[0..3] = AAAA 

Inicialmente:  

occ[A] = 0 
occ[AA] = 0 
occ[AAA] = 0 
occ[AAAA] = 0 

Paso 1: La array LPS de la siguiente string indica la longitud del prefijo más largo, que también es un sufijo: 

LPS[1] denota en la string A A , A es un sufijo y también un prefijo como LPS[1] = 1 
LPS[2] denota en la string A AA , AA es un sufijo y también un prefijo como LPS[2] = 2 
LPS[3] denota en la string A AAA , AAA es un sufijo y también un prefijo como LPS[3] = 3

Paso 2: agregue estas apariciones de prefijos como sufijos a la respuesta en la array   occ[] :

Valores : Substrings contadas 
occ[A] = 1 : S[1] 
occ[AA] = 1 : S[1..2] 
occ[AAA] = 1 : S[1..3] 
occ[AAAA] = 0 : NULL (ya que no hay un prefijo «AAAA» , que también es un sufijo. 
 

Paso 3: ahora recorra la string en orden inverso comenzando desde «AAA» (ya que el último valor siempre será 0 ya que la string completa no es un prefijo adecuado). 

Dado que la string «A AA » S[1..3] también contiene «AA» S[2..3], que aún no se contó, por lo tanto, incremente la aparición de la string «AA» en occ[«AA»] como occ[“AA”] += occ[“AAA”]. A continuación se muestra el recuento de los mismos: 
Valores: substrings contadas 
occ[A] = 1 : S[1] 
occ[AA] = 2 : S[1..2], S[2..3] 
occ[AAA] = 1 : S[1..3] 
occ[AAAA] = 0 : NULO 

Ahora la string “A A ” también contiene “A” , que aún no se contó, por lo tanto, incremente la aparición de la string “A” en occ[“A”] como occ[“A”] += occ[“AA”] . A continuación se muestra el recuento de la misma: 
 

Valores : Substrings contadas 
occ[A] = 3 : S[1], S[2], S[3] 
occ[AA] = 2 : S[1..2], S[2..3] 
occ[AAA ] = 1 : S[1..3] 
occ[AAAA] = 0 : NULO 

Paso 4: Por último, agregue uno a todas las apariciones de los prefijos originales, que aún no se cuentan.  

Valores: substrings contadas 
occ[A] = 4 : S[1], S[2], S[3], S[0] 
occ[AA] = 3 : S[1..2], S[2.. 3], S[0..1] 
occ[AAA] = 2 : S[1..3], S[0..2] 
occ[AAAA] = 1 : S[0..3]  

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 print the count of all
// prefix in the given string
void print(vector<int>& occ, string& s)
{
    // Iterate over string s
    for (int i = 1; i <= int(s.size());
         i++) {
 
        // Print the prefix and their
        // frequency
        cout << s.substr(0, i)
             << " occurs "
             << occ[i]
             << " times."
             << endl;
    }
}
 
// Function to implement the LPS
// array to store the longest prefix
// which is also a suffix for every
// substring of the string S
vector<int> prefix_function(string& s)
{
    // Array to store LPS values
    vector<int> LPS(s.size());
 
    // Value of lps[0] is 0
    // by definition
    LPS[0] = 0;
 
    // Find the values of LPS[i] for
    // the rest of the string using
    // two pointers and DP
    for (int i = 1;
         i < int(s.size());
         i++) {
 
        // Initially set the value
        // of j as the longest
        // prefix that is also a
        // suffix for i as LPS[i-1]
        int j = LPS[i - 1];
 
        // Check if the suffix of
        // length j+1 is also a prefix
        while (j > 0 && s[i] != s[j]) {
            j = LPS[j - 1];
        }
 
        // If s[i] = s[j] then, assign
        // LPS[i] as j+1
        if (s[i] == s[j]) {
            LPS[i] = j + 1;
        }
 
        // If we reached j = 0, assign
        // LPS[i] as 0 as there was no
        // prefix equal to suffix
        else {
            LPS[i] = 0;
        }
    }
 
    // Return the calculated
    // LPS array
    return LPS;
}
 
// Function to count the occurrence
// of all the prefix in the string S
void count_occurrence(string& s)
{
    int n = s.size();
 
    // Call the prefix_function
    // to get LPS
    vector<int> LPS
        = prefix_function(s);
 
    // To store the occurrence of
    // all the prefix
    vector<int> occ(n + 1);
 
    // Count all the suffixes that
    // are also prefix
    for (int i = 0; i < n; i++) {
        occ[LPS[i]]++;
    }
 
    // Add the occurrences of
    // i to smaller prefixes
    for (int i = n - 1;
         i > 0; i--) {
        occ[LPS[i - 1]] += occ[i];
    }
 
    // Adding 1 to all occ[i] for all
    // the original prefix
    for (int i = 0; i <= n; i++)
        occ[i]++;
 
    // Function Call to print the
    // occurrence of all the prefix
    print(occ, s);
}
 
// Driver Code
int main()
{
    // Given String
    string A = "ABACABA";
 
    // Function Call
    count_occurrence(A);
    return 0;
}

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to print the count
// of all prefix in the
// given String
static void print(int[] occ,
                  String s)
{
  // Iterate over String s
  for (int i = 1;
           i <= s.length() - 1; i++)
  {
    // Print the prefix and their
    // frequency
    System.out.print(s.substring(0, i) +
                     " occurs " + occ[i] +
                     " times." + "\n");
  }
}
 
// Function to implement the LPS
// array to store the longest prefix
// which is also a suffix for every
// subString of the String S
static int[] prefix_function(String s)
{
  // Array to store LPS values
  int []LPS = new int[s.length()];
 
  // Value of lps[0] is 0
  // by definition
  LPS[0] = 0;
 
  // Find the values of LPS[i] for
  // the rest of the String using
  // two pointers and DP
  for (int i = 1;
       i < s.length(); i++)
  {
    // Initially set the value
    // of j as the longest
    // prefix that is also a
    // suffix for i as LPS[i-1]
    int j = LPS[i - 1];
 
    // Check if the suffix of
    // length j+1 is also a prefix
    while (j > 0 &&
           s.charAt(i) != s.charAt(j))
    {
      j = LPS[j - 1];
    }
 
    // If s[i] = s[j] then, assign
    // LPS[i] as j+1
    if (s.charAt(i) == s.charAt(j))
    {
      LPS[i] = j + 1;
    }
 
    // If we reached j = 0, assign
    // LPS[i] as 0 as there was no
    // prefix equal to suffix
    else
    {
      LPS[i] = 0;
    }
  }
 
  // Return the calculated
  // LPS array
  return LPS;
}
 
// Function to count the occurrence
// of all the prefix in the String S
static void count_occurrence(String s)
{
  int n = s.length();
 
  // Call the prefix_function
  // to get LPS
  int[] LPS = prefix_function(s);
 
  // To store the occurrence of
  // all the prefix
  int []occ = new int[n + 1];
 
  // Count all the suffixes that
  // are also prefix
  for (int i = 0; i < n; i++)
  {
    occ[LPS[i]]++;
  }
 
  // Add the occurrences of
  // i to smaller prefixes
  for (int i = n - 1;
           i > 0; i--)
  {
    occ[LPS[i - 1]] += occ[i];
  }
 
  // Adding 1 to all occ[i] for all
  // the original prefix
  for (int i = 0; i <= n; i++)
    occ[i]++;
 
  // Function Call to print the
  // occurrence of all the prefix
  print(occ, s);
}
 
// Driver Code
public static void main(String[] args)
{
  // Given String
  String A = "ABACABA";
 
  // Function Call
  count_occurrence(A);
}
}
 
// This code is contributed by Princi Singh

# Python3 program for the above approach
 
# Function to print the count of all
# prefix in the given string
def Print(occ, s):
     
    # Iterate over string s
    for i in range(1, len(s) + 1):
 
        # Print the prefix and their
        # frequency
        print(s[0 : i], "occur", occ[i], "times.")
 
# Function to implement the LPS
# array to store the longest prefix
# which is also a suffix for every
# substring of the string S
def prefix_function(s):
 
    # Array to store LPS values
    # Value of lps[0] is 0
    # by definition
    LPS = [0 for i in range(len(s))]
     
    # Find the values of LPS[i] for
    # the rest of the string using
    # two pointers and DP
    for i in range(1, len(s)):
 
        # Initially set the value
        # of j as the longest
        # prefix that is also a
        # suffix for i as LPS[i-1]
        j = LPS[i - 1]
 
        # Check if the suffix of
        # length j+1 is also a prefix
        while (j > 0 and s[i] != s[j]):
            j = LPS[j - 1]
 
        # If s[i] = s[j] then, assign
        # LPS[i] as j+1
        if (s[i] == s[j]):
            LPS[i] = j + 1
             
        # If we reached j = 0, assign
        # LPS[i] as 0 as there was no
        # prefix equal to suffix
        else:
            LPS[i] = 0
 
    # Return the calculated
    # LPS array
    return LPS
 
# Function to count the occurrence
# of all the prefix in the string S
def count_occurrence(s):
     
    n = len(s)
 
    # Call the prefix_function
    # to get LPS
    LPS = prefix_function(s)
 
    # To store the occurrence of
    # all the prefix
    occ = [0 for i in range(n + 1)]
 
    # Count all the suffixes that
    # are also prefix
    for i in range(n):
        occ[LPS[i]] += 1
 
    # Add the occurrences of
    # i to smaller prefixes
    for i in range(n - 1, 0, -1):
        occ[LPS[i - 1]] += occ[i]
     
    # Adding 1 to all occ[i] for all
    # the original prefix
    for i in range(n + 1):
        occ[i] += 1
         
    # Function Call to print the
    # occurrence of all the prefix
    Print(occ, s)
 
# Driver Code
 
# Given String
A = "ABACABA"
 
# Function Call
count_occurrence(A)
 
# This code is contributed by avanitrachhadiya2155

// C# program for
// the above approach
using System;
class GFG{
 
// Function to print the
// count of all prefix
// in the given String
static void print(int[] occ,
                  String s)
{
  // Iterate over String s
  for (int i = 1;
           i <= s.Length - 1; i++)
  {
    // Print the prefix and their
    // frequency
    Console.Write(s.Substring(0, i) + 
                  " occurs " + occ[i] + 
                  " times." + "\n");
  }
}
 
// Function to implement the LPS
// array to store the longest prefix
// which is also a suffix for every
// subString of the String S
static int[] prefix_function(String s)
{
  // Array to store LPS values
  int []LPS = new int[s.Length];
 
  // Value of lps[0] is 0
  // by definition
  LPS[0] = 0;
 
  // Find the values of LPS[i] for
  // the rest of the String using
  // two pointers and DP
  for (int i = 1;
           i < s.Length; i++)
  {
    // Initially set the value
    // of j as the longest
    // prefix that is also a
    // suffix for i as LPS[i-1]
    int j = LPS[i - 1];
 
    // Check if the suffix of
    // length j+1 is also a prefix
    while (j > 0 && s[i] != s[j])
    {
      j = LPS[j - 1];
    }
 
    // If s[i] = s[j] then,
    // assign LPS[i] as j+1
    if (s[i] == s[j])
    {
      LPS[i] = j + 1;
    }
 
    // If we reached j = 0, assign
    // LPS[i] as 0 as there was no
    // prefix equal to suffix
    else
    {
      LPS[i] = 0;
    }
  }
 
  // Return the calculated
  // LPS array
  return LPS;
}
 
// Function to count the occurrence
// of all the prefix in the String S
static void count_occurrence(String s)
{
  int n = s.Length;
 
  // Call the prefix_function
  // to get LPS
  int[] LPS = prefix_function(s);
 
  // To store the occurrence of
  // all the prefix
  int []occ = new int[n + 1];
 
  // Count all the suffixes that
  // are also prefix
  for (int i = 0; i < n; i++)
  {
    occ[LPS[i]]++;
  }
 
  // Add the occurrences of
  // i to smaller prefixes
  for (int i = n - 1;
           i > 0; i--)
  {
    occ[LPS[i - 1]] += occ[i];
  }
 
  // Adding 1 to all occ[i] for all
  // the original prefix
  for (int i = 0; i <= n; i++)
    occ[i]++;
 
  // Function Call to print the
  // occurrence of all the prefix
  print(occ, s);
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given String
  String A = "ABACABA";
 
  // Function Call
  count_occurrence(A);
}
}
 
// This code is contributed by Amit Katiyar

<script>
    // JavaScript program for the above approach
 
    // Function to print the count of all
    // prefix in the given string
    const print = (occ, s) => {
        // Iterate over string s
        for (let i = 1; i <= s.length; i++) {
 
            // Print the prefix and their
            // frequency
            document.write(`${s.substr(0, i)} occurs ${occ[i]} times.<br/>`);
        }
    }
 
    // Function to implement the LPS
    // array to store the longest prefix
    // which is also a suffix for every
    // substring of the string S
    const prefix_function = (s) => {
        // Array to store LPS values
        let LPS = new Array(s.length).fill(0);
 
        // Value of lps[0] is 0
        // by definition
        LPS[0] = 0;
 
        // Find the values of LPS[i] for
        // the rest of the string using
        // two pointers and DP
        for (let i = 1; i < s.length; i++) {
 
            // Initially set the value
            // of j as the longest
            // prefix that is also a
            // suffix for i as LPS[i-1]
            let j = LPS[i - 1];
 
            // Check if the suffix of
            // length j+1 is also a prefix
            while (j > 0 && s[i] != s[j]) {
                j = LPS[j - 1];
            }
 
            // If s[i] = s[j] then, assign
            // LPS[i] as j+1
            if (s[i] == s[j]) {
                LPS[i] = j + 1;
            }
 
            // If we reached j = 0, assign
            // LPS[i] as 0 as there was no
            // prefix equal to suffix
            else {
                LPS[i] = 0;
            }
        }
 
        // Return the calculated
        // LPS array
        return LPS;
    }
 
    // Function to count the occurrence
    // of all the prefix in the string S
    const count_occurrence = (s) => {
        let n = s.length;
 
        // Call the prefix_function
        // to get LPS
        let LPS = prefix_function(s);
 
        // To store the occurrence of
        // all the prefix
        let occ = new Array(n + 1).fill(0);
 
        // Count all the suffixes that
        // are also prefix
        for (let i = 0; i < n; i++) {
            occ[LPS[i]]++;
        }
 
        // Add the occurrences of
        // i to smaller prefixes
        for (let i = n - 1;
            i > 0; i--) {
            occ[LPS[i - 1]] += occ[i];
        }
 
        // Adding 1 to all occ[i] for all
        // the original prefix
        for (let i = 0; i <= n; i++)
            occ[i]++;
 
        // Function Call to print the
        // occurrence of all the prefix
        print(occ, s);
    }
 
    // Driver Code
 
    // Given String
    let A = "ABACABA";
 
    // Function Call
    count_occurrence(A);
 
    // This code is contributed by rakeshsahni
 
</script>

A occurs 4 times.
AB occurs 2 times.
ABA occurs 2 times.
ABAC occurs 1 times.
ABACA occurs 1 times.
ABACAB occurs 1 times.
ABACABA occurs 1 times.

Tiempo Complejidad: O(N ² )  
Espacio Auxiliar: O(N)