Encuentre la array de sufijos de la string dada sin carácter repetido

Posted on by Rudeus Greyrat

Dada una string str de tamaño N , la tarea es encontrar la array de sufijos de la string dada.

Nota: una array de sufijos es una array ordenada de todos los sufijos de una string determinada.

Ejemplos: 

Entrada: str = “prince”
Salida: 4 5 2 3 0 1
Explicación: Los sufijos son
0 prince 4 ce
1 rince Ordenar los sufijos 5 e  
2 ince          —————->    2 ince  
3 nce alfabéticamente 3 nce    
4 ce 0 príncipe
5 y 1 príncipe

Entrada: str = “abcd”
Salida: 0 1 2 3

 

Enfoque: los métodos de búsqueda de arrays de sufijos para cualquier string se analizan aquí . En este artículo, la atención se centra en encontrar una array de sufijos para strings sin caracteres repetidos. Es un problema simple basado en la implementación. Siga los pasos que se mencionan a continuación para resolver el problema:

  • Cuente la aparición de cada carácter.
  • Encuentra la suma del prefijo.
  • Encuentre la array de inicio por start[0] = 0, start[i+1] = prefix[i] para todo i > 0 .
  • Encuentre la array de inicio que contiene el índice de la substring (sufijo) con el carácter inicial de la columna respectiva.

Siga la ilustración a continuación para una mejor comprensión.

Ilustración:

Considere la string «príncipe» :
a continuación se muestra la tabla de sufijos 

carbonizarse a b C d mi F gramo h i j k yo metro norte o pags q r s t tu v w X y z
contar 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0
prefijo 0 0 1 1 2 2 2 2 3 3 3 3 3 4 4 5 5 6 6 6 6 6 6 6 6 6
comienzo 0 0 0 1 1 2 2 2 2 3 3 3 3 3 4 4 5 5 6 6 6 6 6 6 6 6

Para char ‘r’ el valor inicial es 5 . 
Implica una substring (sufijo) que comienza con char ‘r’, es decir, «rince» tiene rango 5.
El rango es la posición en la array de sufijos. (1 «rince») implica la quinta posición en la array de sufijos), consulte la primera tabla.
Del mismo modo, el valor inicial de char ‘n’ es 3 . Implica (3 «nce») 3ra posición en la array de sufijos.

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

C++

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the suffix array
void suffixArray(string str, int N)
{
    // arr[] is array to count
    // occurrence of each character
    int arr[30] = { 0 };
    for (int i = 0; i < N; i++) {
        arr[str[i] - 'a']++;
    }
 
    // Finding prefix count of character
    for (int i = 1; i < 30; i++) {
        arr[i] = arr[i] + arr[i - 1];
    }
 
    int start[30];
    start[0] = 0;
    for (int i = 0; i < 29; i++) {
        start[i + 1] = arr[i];
    }
 
    int ans[N] = { 0 };
 
    // Iterating string in reverse order
    for (int i = N - 1; i >= 0; i--) {
 
        // Storing suffix array in ans[]
        ans[start[str[i] - 'a']] = i;
    }
 
    for (int i = 0; i < N; i++)
        cout << ans[i] << " ";
}
 
// Driver code
int main()
{
    string str = "prince";
    int N = str.length();
 
    suffixArray(str, N);
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
 
  // Function to calculate the suffix array
  static void suffixArray(String str, int N)
  {
 
    // arr[] is array to count
    // occurrence of each character
    int arr[] = new int[30];
    for (int i = 0; i < N; i++) {
      arr[str.charAt(i) - 'a']++;
    }
 
    // Finding prefix count of character
    for (int i = 1; i < 30; i++) {
      arr[i] = arr[i] + arr[i - 1];
    }
 
    int start[] = new int[30];
    start[0] = 0;
    for (int i = 0; i < 29; i++) {
      start[i + 1] = arr[i];
    }
 
    int ans[]  = new int[N];
 
    // Iterating string in reverse order
    for (int i = N - 1; i >= 0; i--) {
 
      // Storing suffix array in ans[]
      ans[start[str.charAt(i) - 'a']] = i;
    }
 
    for (int i = 0; i < N; i++)
      System.out.print(ans[i] + " ");
  }
 
  // Driver code
  public static void main (String[] args)
  {
    String str = "prince";
    int N = str.length();
 
    suffixArray(str, N);
  }
}
 
// This code is contributed by hrithikgarg03188

Python3

# Python code for the above approach
 
# Function to calculate the suffix array
def suffixArray(str, N):
   
    # arr[] is array to count
    # occurrence of each character
    arr = [0] * 30
    for i in range(N):
        arr[ord(str[i]) - ord('a')] += 1
 
    # Finding prefix count of character
    for i in range(1, 30):
        arr[i] = arr[i] + arr[i - 1]
 
    start = [0] * 30
    start[0] = 0
    for i in range(29):
        start[i + 1] = arr[i]
 
    ans = [0] * N
 
    # Iterating string in reverse order
    for i in range(N - 1, 0, -1):
 
        # Storing suffix array in ans[]
        ans[start[ord(str[i]) - ord('a')]] = i
 
    for i in range(N):
        print(ans[i], end=" ")
 
# Driver code
str = "prince"
N = len(str)
 
suffixArray(str, N)
 
# This code is contributed by gfgking

C#

// C# code to implement above approach
using System;
class GFG
{
   
    // Function to calculate the suffix array
    static void suffixArray(string str, int N)
    {
        // arr[] is array to count
        // occurrence of each character
        int[] arr = new int[30];
        for (int i = 0; i < N; i++) {
            arr[str[i] - 'a']++;
        }
 
        // Finding prefix count of character
        for (int i = 1; i < 30; i++) {
            arr[i] = arr[i] + arr[i - 1];
        }
 
        int[] start = new int[30];
        start[0] = 0;
        for (int i = 0; i < 29; i++) {
            start[i + 1] = arr[i];
        }
 
        int[] ans = new int[N];
 
        // Iterating string in reverse order
        for (int i = N - 1; i >= 0; i--) {
 
            // Storing suffix array in ans[]
            ans[start[str[i] - 'a']] = i;
        }
 
        for (int i = 0; i < N; i++) {
            Console.Write(ans[i]);
            Console.Write(" ");
        }
    }
 
    // Driver code
    public static int Main()
    {
        string str = "prince";
        int N = str.Length;
 
        suffixArray(str, N);
        return 0;
    }
}
 
// This code is contributed by Taranpreet

Javascript

<script>
     // JavaScript code for the above approach
 
 
     // Function to calculate the suffix array
     function suffixArray(str, N) {
         // arr[] is array to count
         // occurrence of each character
         let arr = new Array(30).fill(0);
         for (let i = 0; i < N; i++) {
             arr[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
         }
 
         // Finding prefix count of character
         for (let i = 1; i < 30; i++) {
             arr[i] = arr[i] + arr[i - 1];
         }
 
         let start = new Array(30)
         start[0] = 0;
         for (let i = 0; i < 29; i++) {
             start[i + 1] = arr[i];
         }
 
         let ans = new Array(N).fill(0)
 
         // Iterating string in reverse order
         for (let i = N - 1; i >= 0; i--) {
 
             // Storing suffix array in ans[]
             ans[start[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]] = i;
         }
 
         for (let i = 0; i < N; i++)
             document.write(ans[i] + " ")
     }
 
     // Driver code
 
     let str = "prince";
     let N = str.length;
 
     suffixArray(str, N);
 
 
      // This code is contributed by Potta Lokesh
 </script>
Producción

4 5 2 3 0 1

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

Publicación traducida automáticamente

Artículo escrito por pptwo7 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *