Dada la string str , la tarea es encontrar el rango de la string dada entre todas sus substrings ordenadas lexicográficamente.
Ejemplos:
Entrada: S = “enren”
Salida: 7
Explicación:
Todas las substrings posibles en el orden ordenado son {“e”, “e”, “en”, “en”, “enr”, “enre”, “enren”, “n”, “n”, “nr”, “nre”, “nren”, “r”, “re”, “ren”}.
Por lo tanto, el rango de la string dada “enren” es 7.Entrada: S = “geeks”
Salida: 12
Explicación:
Todas las substrings posibles en el orden ordenado son {“e”, “e”, “ee”, “eek”, “eeks”, “ek”, “eks”, “ g”, “ge”, “gee”, “geek”, “geeks”, “k”, “ks”, “s”}.
Por lo tanto, el rango de la string dada «geeks» es 12.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una array arr[] de vectores de longitud 26 para almacenar los índices de los caracteres presentes en la string y clasifíquelos como 0.
- Almacena los índices de cada carácter. Los índices de a se almacenarán en arr[0] , para b , arr[1] almacenará todos sus índices, y así sucesivamente.
- Recorra cada índice almacenado en la array arr[] hasta los caracteres que son más pequeños que el primer carácter de la string S .
- Para cada índice i , el total de substrings a partir de ese índice es N – i . Agregue N – i para clasificar , ya que todos los caracteres con estos índices son más pequeños.
- Ahora, después de atravesar, almacene todas las substrings a partir del primer carácter de S y ordene esas substrings en orden lexicográfico.
- Recorra las substrings ordenadas y compare cada substring con la string S e incremente el rango hasta que se encuentre la substring igual a S.
- Imprime el valor de rango + 1 para obtener el rango de la string dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find lexicographic rank
// of string among all its substring
int lexicographicRank(string s)
{
// Length of string
int n = s.length();
vector<int> alphaIndex[26];
// Traverse the given string
// and store the indices of
// each character
for (int i = 0; i < s.length(); i++) {
// Extract the index
int x = s[i] - 'a';
// Store it in the vector
alphaIndex[x].push_back(i);
}
// Traverse the alphaIndex array
// lesser than the index of first
// character of given string
int rank = 0;
for (int i = 0; i < 26
&& 'a' + i < s[0];
i++) {
// If alphaIndex[i] size exceeds 0
if (alphaIndex[i].size() > 0) {
// Traverse over the indices
for (int j = 0;
j < alphaIndex[i].size(); j++) {
// Add count of substring
// equal to n - alphaIndex[i][j]
rank = rank
+ (n
- alphaIndex[i][j]);
}
}
}
vector<string> str;
for (int i = 0;
i < alphaIndex[s[0] - 'a'].size();
i++) {
// Store all substrings in a vector
// str starting with the first
// character of the given string
string substring;
int j = alphaIndex[s[0] - 'a'][i];
for (; j < n; j++) {
// Insert the current
// character to substring
substring.push_back(s[j]);
// Store the substring formed
str.push_back(substring);
}
}
// Sort the substring in the
// lexicographical order
sort(str.begin(), str.end());
// Find the rank of given string
for (int i = 0; i < str.size(); i++) {
if (str[i] != s) {
// increase the rank until
// the given string is same
rank++;
}
// If substring is same as
// the given string
else {
break;
}
}
// Add 1 to rank of
// the given string
return rank + 1;
}
// Driver Code
int main()
{
// Given string
string str = "enren";
// Function Call
cout << lexicographicRank(str);
return 0;
}
Java
// Java program for
// the above approach
import java.util.*;
class GFG{
// Function to find lexicographic rank
// of String among all its subString
static int lexicographicRank(char []s)
{
// Length of String
int n = s.length;
Vector<Integer> []alphaIndex = new Vector[26];
for (int i = 0; i < alphaIndex.length; i++)
alphaIndex[i] = new Vector<Integer>();
// Traverse the given String
// and store the indices of
// each character
for (int i = 0; i < s.length; i++)
{
// Extract the index
int x = s[i] - 'a';
// Store it in the vector
alphaIndex[x].add(i);
}
// Traverse the alphaIndex array
// lesser than the index of first
// character of given String
int rank = 0;
for (int i = 0; i < 26 &&
'a' + i < s[0]; i++)
{
// If alphaIndex[i] size exceeds 0
if (alphaIndex[i].size() > 0)
{
// Traverse over the indices
for (int j = 0;
j < alphaIndex[i].size();
j++)
{
// Add count of subString
// equal to n - alphaIndex[i][j]
rank = rank + (n - alphaIndex[i].get(j));
}
}
}
Vector<String> str = new Vector<String>();
for (int i = 0;
i < alphaIndex[s[0] - 'a'].size();
i++)
{
// Store all subStrings in a vector
// str starting with the first
// character of the given String
String subString = "";
int j = alphaIndex[s[0] - 'a'].get(i);
for (; j < n; j++)
{
// Insert the current
// character to subString
subString += (s[j]);
// Store the subString formed
str.add(subString);
}
}
// Sort the subString in the
// lexicographical order
Collections.sort(str);
// Find the rank of given String
for (int i = 0; i < str.size(); i++)
{
if (!str.get(i).equals(String.valueOf(s)))
{
// increase the rank until
// the given String is same
rank++;
}
// If subString is same as
// the given String
else
{
break;
}
}
// Add 1 to rank of
// the given String
return rank + 1;
}
// Driver Code
public static void main(String[] args)
{
// Given String
String str = "enren";
// Function Call
System.out.print(lexicographicRank(str.toCharArray()));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach
# Function to find lexicographic rank
# of among all its substring
def lexicographicRank(s):
# Length of string
n = len(s)
alphaIndex = [[] for i in range(26)]
# Traverse the given string
# and store the indices of
# each character
for i in range(len(s)):
# Extract the index
x = ord(s[i]) - ord('a')
# Store it in the vector
alphaIndex[x].append(i)
# Traverse the alphaIndex array
# lesser than the index of first
# character of given string
rank = -1
for i in range(26):
if ord('a') + i >= ord(s[0]):
break
# If alphaIndex[i] size exceeds 0
if len(alphaIndex[i]) > 0:
# Traverse over the indices
for j in range(len(alphaIndex[i])):
# Add count of substring
# equal to n - alphaIndex[i][j]
rank = rank + (n - alphaIndex[i][j])
# print(rank)
strr = []
for i in range(len(alphaIndex[ord(s[0]) - ord('a')])):
# Store all substrings in a vector
# strr starting with the first
# character of the given string
substring = []
jj = alphaIndex[ord(s[0]) - ord('a')][i]
for j in range(jj, n):
# Insert the current
# character to substring
substring.append(s[j])
# Store the subformed
strr.append(substring)
# Sort the substring in the
# lexicographical order
strr = sorted(strr)
# Find the rank of given string
for i in range(len(strr)):
if (strr[i] != s):
# Increase the rank until
# the given is same
rank += 1
# If substring is same as
# the given string
else:
break
# Add 1 to rank of
# the given string
return rank + 1
# Driver Code
if __name__ == '__main__':
# Given string
strr = "enren"
# Function call
print(lexicographicRank(strr))
# 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 lexicographic rank
// of String among all its subString
static int lexicographicRank(char []s)
{
// Length of String
int n = s.Length;
List<int> []alphaIndex = new List<int>[26];
for (int i = 0; i < alphaIndex.Length; i++)
alphaIndex[i] = new List<int>();
// Traverse the given String
// and store the indices of
// each character
for (int i = 0; i < s.Length; i++)
{
// Extract the index
int x = s[i] - 'a';
// Store it in the vector
alphaIndex[x].Add(i);
}
// Traverse the alphaIndex array
// lesser than the index of first
// character of given String
int rank = 0;
for (int i = 0; i < 26 &&
'a' + i < s[0]; i++)
{
// If alphaIndex[i] size exceeds 0
if (alphaIndex[i].Count > 0)
{
// Traverse over the indices
for (int j = 0;
j < alphaIndex[i].Count; j++)
{
// Add count of subString
// equal to n - alphaIndex[i,j]
rank = rank + (n - alphaIndex[i][j]);
}
}
}
List<String> str = new List<String>();
for (int i = 0;
i < alphaIndex[s[0] - 'a'].Count; i++)
{
// Store all subStrings in a vector
// str starting with the first
// character of the given String
String subString = "";
int j = alphaIndex[s[0] - 'a'][i];
for (; j < n; j++)
{
// Insert the current
// character to subString
subString += (s[j]);
// Store the subString formed
str.Add(subString);
}
}
// Sort the subString in the
// lexicographical order
str.Sort();
// Find the rank of given String
for (int i = 0; i < str.Count; i++)
{
if (!str[i].Equals(String.Join("", s)))
{
// increase the rank until
// the given String is same
rank++;
}
// If subString is same as
// the given String
else
{
break;
}
}
// Add 1 to rank of
// the given String
return rank + 1;
}
// Driver Code
public static void Main(String[] args)
{
// Given String
String str = "enren";
// Function Call
Console.Write(lexicographicRank(str.ToCharArray()));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to find lexicographic rank
// of string among all its substring
function lexicographicRank(s)
{
// Length of string
var n = s.length;
var alphaIndex = Array.from(Array(26),
()=>new Array());
// Traverse the given string
// and store the indices of
// each character
for (var i = 0; i < s.length; i++) {
// Extract the index
var x = s[i].charCodeAt(0) -
'a'.charCodeAt(0);
// Store it in the vector
alphaIndex[x].push(i);
}
// Traverse the alphaIndex array
// lesser than the index of first
// character of given string
var rank = 0;
for (var i = 0; i < 26
&& 'a'.charCodeAt(0) +
i < s[0].charCodeAt(0);
i++) {
// If alphaIndex[i] size exceeds 0
if (alphaIndex[i].length > 0) {
// Traverse over the indices
for (var j = 0;
j < alphaIndex[i].length; j++) {
// Add count of substring
// equal to n - alphaIndex[i][j]
rank = rank
+ (n
- alphaIndex[i][j]);
}
}
}
var str = [];
for (var i = 0;
i < alphaIndex[s[0].charCodeAt(0) -
'a'.charCodeAt(0)].length;
i++) {
// Store all substrings in a vector
// str starting with the first
// character of the given string
var substring = "";
var j = alphaIndex[s[0].charCodeAt(0) -
'a'.charCodeAt(0)][i];
for (; j < n; j++) {
// Insert the current
// character to substring
substring+=(s[j]);
// Store the substring formed
str.push(substring);
}
}
// Sort the substring in the
// lexicographical order
str.sort();
// Find the rank of given string
for (var i = 0; i < str.length; i++) {
if (str[i] != s) {
// increase the rank until
// the given string is same
rank++;
}
// If substring is same as
// the given string
else {
break;
}
}
// Add 1 to rank of
// the given string
return rank + 1;
}
// Driver Code
// Given string
var str = "enren";
// Function Call
document.write( lexicographicRank(str));
</script>
Producción:
7
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)