Dada una string str , sus substrings se forman de tal manera que todas las substrings que comienzan con el primer carácter de la string aparecerán primero en el orden ordenado de sus longitudes, seguidas por todas las substrings que comienzan con el segundo carácter de la string en el orden ordenado de sus longitudes y así sucesivamente.
Por ejemplo, para la string abc , sus substrings en el orden requerido son a , ab , abc , b , bc y c .
Ahora dado un entero k , la tarea es encontrar la k-ésima substring en el orden requerido.
Ejemplos:
Entrada: str = abc, k = 4
Salida: b
El orden requerido es “a”, “ab”, “abc”, “b”, “bc” y “c”
Entrada: str = abc, k = 9
Salida: -1
Solo son posibles 6 substrings.
Enfoque: La idea es utilizar la búsqueda binaria . Se utilizará una substring de array para almacenar el número de substrings que comienzan con i-ésimo carácter + substring[i – 1]. Ahora, usando la búsqueda binaria en la substring de la array , encuentre el índice inicial de la substring requerida y luego busque el índice final para la misma substring con end = length_of_string – (substring[start] – k).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to prints kth sub-string
void Printksubstring(string str, int n, int k)
{
// Total sub-strings possible
int total = (n * (n + 1)) / 2;
// If k is greater than total
// number of sub-strings
if (k > total) {
printf("-1\n");
return;
}
// To store number of sub-strings starting
// with ith character of the string
int substring[n + 1];
substring[0] = 0;
// Compute the values
int temp = n;
for (int i = 1; i <= n; i++) {
// substring[i - 1] is added
// to store the cumulative sum
substring[i] = substring[i - 1] + temp;
temp--;
}
// Binary search to find the starting index
// of the kth sub-string
int l = 1;
int h = n;
int start = 0;
while (l <= h) {
int m = (l + h) / 2;
if (substring[m] > k) {
start = m;
h = m - 1;
}
else if (substring[m] < k)
l = m + 1;
else {
start = m;
break;
}
}
// To store the ending index of
// the kth sub-string
int end = n - (substring[start] - k);
// Print the sub-string
for (int i = start - 1; i < end; i++)
cout << str[i];
}
// Driver code
int main()
{
string str = "abc";
int k = 4;
int n = str.length();
Printksubstring(str, n, k);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to prints kth sub-string
static void Printksubstring(String str, int n, int k)
{
// Total sub-strings possible
int total = (n * (n + 1)) / 2;
// If k is greater than total
// number of sub-strings
if (k > total)
{
System.out.printf("-1\n");
return;
}
// To store number of sub-strings starting
// with ith character of the string
int substring[] = new int[n + 1];
substring[0] = 0;
// Compute the values
int temp = n;
for (int i = 1; i <= n; i++)
{
// substring[i - 1] is added
// to store the cumulative sum
substring[i] = substring[i - 1] + temp;
temp--;
}
// Binary search to find the starting index
// of the kth sub-string
int l = 1;
int h = n;
int start = 0;
while (l <= h)
{
int m = (l + h) / 2;
if (substring[m] > k)
{
start = m;
h = m - 1;
}
else if (substring[m] < k)
{
l = m + 1;
}
else
{
start = m;
break;
}
}
// To store the ending index of
// the kth sub-string
int end = n - (substring[start] - k);
// Print the sub-string
for (int i = start - 1; i < end; i++)
{
System.out.print(str.charAt(i));
}
}
// Driver code
public static void main(String[] args)
{
String str = "abc";
int k = 4;
int n = str.length();
Printksubstring(str, n, k);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 implementation of the approach
# Function to prints kth sub-string
def Printksubstring(str1, n, k):
# Total sub-strings possible
total = int((n * (n + 1)) / 2)
# If k is greater than total
# number of sub-strings
if (k > total):
print("-1")
return
# To store number of sub-strings starting
# with ith character of the string
substring = [0 for i in range(n + 1)]
substring[0] = 0
# Compute the values
temp = n
for i in range(1, n + 1, 1):
# substring[i - 1] is added
# to store the cumulative sum
substring[i] = substring[i - 1] + temp
temp -= 1
# Binary search to find the starting index
# of the kth sub-string
l = 1
h = n
start = 0
while (l <= h):
m = int((l + h) / 2)
if (substring[m] > k):
start = m
h = m - 1
elif (substring[m] < k):
l = m + 1
else:
start = m
break
# To store the ending index of
# the kth sub-string
end = n - (substring[start] - k)
# Print the sub-string
for i in range(start - 1, end):
print(str1[i], end = "")
# Driver code
if __name__ == '__main__':
str1 = "abc"
k = 4
n = len(str1)
Printksubstring(str1, n, k)
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to prints kth sub-string
static void Printksubstring(String str, int n, int k)
{
// Total sub-strings possible
int total = (n * (n + 1)) / 2;
// If k is greater than total
// number of sub-strings
if (k > total)
{
Console.Write("-1\n");
return;
}
// To store number of sub-strings starting
// with ith character of the string
int []substring = new int[n + 1];
substring[0] = 0;
// Compute the values
int temp = n;
for (int i = 1; i <= n; i++)
{
// substring[i - 1] is added
// to store the cumulative sum
substring[i] = substring[i - 1] + temp;
temp--;
}
// Binary search to find the starting index
// of the kth sub-string
int l = 1;
int h = n;
int start = 0;
while (l <= h)
{
int m = (l + h) / 2;
if (substring[m] > k)
{
start = m;
h = m - 1;
}
else if (substring[m] < k)
{
l = m + 1;
}
else
{
start = m;
break;
}
}
// To store the ending index of
// the kth sub-string
int end = n - (substring[start] - k);
// Print the sub-string
for (int i = start - 1; i < end; i++)
{
Console.Write(str[i]);
}
}
// Driver code
public static void Main(String[] args)
{
String str = "abc";
int k = 4;
int n = str.Length;
Printksubstring(str, n, k);
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP implementation of the approach
// Function to prints kth sub-string
function Printksubstring($str, $n, $k)
{
// Total sub-strings possible
$total = floor(($n * ($n + 1)) / 2);
// If k is greater than total
// number of sub-strings
if ($k > $total)
{
printf("-1\n");
return;
}
// To store number of sub-strings starting
// with ith character of the string
$substring = array();
$substring[0] = 0;
// Compute the values
$temp = $n;
for ($i = 1; $i <= $n; $i++)
{
// substring[i - 1] is added
// to store the cumulative sum
$substring[$i] = $substring[$i - 1] + $temp;
$temp--;
}
// Binary search to find the starting index
// of the kth sub-string
$l = 1;
$h = $n;
$start = 0;
while ($l <= $h)
{
$m = floor(($l + $h) / 2);
if ($substring[$m] > $k)
{
$start = $m;
$h = $m - 1;
}
else if ($substring[$m] < $k)
$l = $m + 1;
else
{
$start = $m;
break;
}
}
// To store the ending index of
// the kth sub-string
$end = $n - ($substring[$start] - $k);
// Print the sub-string
for ($i = $start - 1; $i < $end; $i++)
print($str[$i]);
}
// Driver code
$str = "abc";
$k = 4;
$n = strlen($str);
Printksubstring($str, $n, $k);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to prints kth sub-string
function Printksubstring(str, n, k)
{
// Total sub-strings possible
let total = parseInt((n * (n + 1)) / 2, 10);
// If k is greater than total
// number of sub-strings
if (k > total)
{
document.write("-1" + "</br>");
return;
}
// To store number of sub-strings starting
// with ith character of the string
let substring = new Array(n + 1);
substring[0] = 0;
// Compute the values
let temp = n;
for (let i = 1; i <= n; i++)
{
// substring[i - 1] is added
// to store the cumulative sum
substring[i] = substring[i - 1] + temp;
temp--;
}
// Binary search to find the starting index
// of the kth sub-string
let l = 1;
let h = n;
let start = 0;
while (l <= h)
{
let m = parseInt((l + h) / 2, 10);
if (substring[m] > k)
{
start = m;
h = m - 1;
}
else if (substring[m] < k)
{
l = m + 1;
}
else
{
start = m;
break;
}
}
// To store the ending index of
// the kth sub-string
let end = n - (substring[start] - k);
// Print the sub-string
for (let i = start - 1; i < end; i++)
{
document.write(str[i]);
}
}
let str = "abc";
let k = 4;
let n = str.length;
Printksubstring(str, n, k);
//This code is contributed by divyeshrabadiya07.
</script>
Producción:
b
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA