Se proporciona una string que define un número válido. Muestra todas las conversiones base de substrings de longitud ‘k’ desde la base ‘b’ a la base 10.
Ejemplos:
Input : str = "12212",
k = 3, b = 3.
Output : 17 25 23
Explanation :
All the substrings of length 'k' are : 122, 221, 212.
Base conversion can be computed using the formula.
Método 1 (Simple): Un enfoque simple es usar una técnica de conversión de base simple. Para un número base b str, su equivalente decimal es str[0]*b 0 + str[1]*b 1 + str[2]*b 2 + … + str[n-1]*b n-1
Implementación:
C++
// Simple C++ program to convert all substrings from
// decimal to given base.
#include <bits/stdc++.h>
using namespace std;
int substringConversions(string str, int k, int b)
{
for (int i=0; i + k <= str.size(); i++)
{
// Saving substring in sub
string sub = str.substr(i, k);
// Evaluating decimal for current substring
// and printing it.
int sum = 0, counter = 0;
for (int i = sub.size() - 1; i >= 0; i--)
{
sum = sum + ((sub.at(i) - '0') * pow(b, counter));
counter++;
}
cout << sum << " ";
}
}
// Driver code
int main()
{
string str = "12212";
int b = 3, k = 3;
substringConversions(str, b, k);
return 0;
}
Java
// Simple Java program to convert all substrings from
// decimal to given base.
class GFG
{
static void substringConversions(String str, int k, int b)
{
for (int i=0; i + k <= str.length(); i++)
{
// Saving substring in sub
String sub = str.substring(i, i+k);
// Evaluating decimal for current substring
// and printing it.
int sum = 0, counter = 0;
for (int j = sub.length() - 1; j >= 0; j--)
{
sum = (int) (sum + ((sub.charAt(j) - '0') *
Math.pow(b, counter)));
counter++;
}
System.out.print(sum + " ");
}
}
// Driver code
public static void main(String[] args)
{
String str = "12212";
int b = 3, k = 3;
substringConversions(str, b, k);
}
}
// This code is contributed by 29AjayKumar
Python3
# Simple Python3 program to convert
# all substrings from decimal to given base.
import math
def substringConversions(s, k, b):
l = len(s);
for i in range(l):
if((i + k) < l + 1):
# Saving substring in sub
sub = s[i : i + k];
# Evaluating decimal for current
# substring and printing it.
sum, counter = 0, 0;
for i in range(len(sub) - 1, -1, -1):
sum = sum + ((ord(sub[i]) - ord('0')) *
pow(b, counter));
counter += 1;
print(sum , end = " ");
# Driver code
s = "12212";
b, k = 3, 3;
substringConversions(s, b, k);
# This code is contributed
# by Princi Singh
C#
// Simple C# program to convert all substrings from
// decimal to given base.
using System;
class GFG
{
static void substringConversions(String str, int k, int b)
{
for (int i = 0; i + k <= str.Length; i++)
{
// Saving substring in sub
String sub = str.Substring(i, k);
// Evaluating decimal for current substring
// and printing it.
int sum = 0, counter = 0;
for (int j = sub.Length - 1; j >= 0; j--)
{
sum = (int) (sum + ((sub[j] - '0') *
Math.Pow(b, counter)));
counter++;
}
Console.Write(sum + " ");
}
}
// Driver code
public static void Main(String[] args)
{
String str = "12212";
int b = 3, k = 3;
substringConversions(str, b, k);
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// Simple Javascript program to convert
// all substrings from decimal to given base.
function substringConversions(str, k, b)
{
for(let i = 0; i + k <= str.length; i++)
{
// Saving substring in sub
let sub = str.substring(i, i+k);
// Evaluating decimal for current substring
// and printing it.
let sum = 0, counter = 0;
for(let j = sub.length - 1; j >= 0; j--)
{
sum = (sum + ((sub[j].charCodeAt(0) -
'0'.charCodeAt(0)) *
Math.pow(b, counter)));
counter++;
}
document.write(sum + " ");
}
}
// Driver code
let str = "12212";
let b = 3, k = 3;
substringConversions(str, b, k);
// This code is contributed by patel2127
</script>
Producción
17 25 23
Complejidad temporal: O(n*k)
Espacio auxiliar: O(n)
Método 2 (Usando ventana deslizante): Podemos usar la técnica de Ventana deslizante para resolverlo en tiempo lineal. Cada vez que deslicemos la ventana, restaremos el peso del primer elemento, es decir, (elemento * pow(b, k-1)) . Ahora, multiplicar la suma anterior con ‘b’ aumentará el peso de cada elemento 3 veces lo que se requiere. Además, simplemente agregaremos el nuevo elemento en la ventana porque su peso será element * pow(b, 0) .
A continuación se muestra la implementación:
C++
// Efficient C++ program to convert all substrings from
// decimal to given base.
#include <bits/stdc++.h>
using namespace std;
int substringConversions(string str, int k, int b)
{
int i = 0, sum = 0, counter = k-1;
// Computing the decimal of first window
for (i; i < k; i++)
{
sum = sum + ((str.at(i) - '0') * pow(b, counter));
counter--;
}
cout << sum << " ";
// prev stores the previous decimal
int prev = sum;
// Computing decimal equivalents of all other windows
sum = 0, counter = 0;
for (i; i < str.size(); i++)
{
// Subtracting weight of the element pushed out of window
sum = prev - ((str.at(i - k) - '0') * pow(b, k-1));
// Multiplying the decimal by base to formulate other window
sum = sum * b;
// Adding the new element of window to sum
sum = sum + (str.at(i) - '0');
// Decimal of current window
cout << sum << " ";
// Updating prev
prev = sum;
counter++;
}
}
// Driver code
int main()
{
string str = "12212";
int b = 3, k = 3;
substringConversions(str, b, k);
return 0;
}
Java
// Efficient Java program to convert
// all substrings from decimal to given base.
import java.util.*;
class GFG
{
static void substringConversions(String str,
int k, int b)
{
int i = 0, sum = 0, counter = k-1;
// Computing the decimal of first window
for (i = 0; i < k; i++)
{
sum = (int) (sum + ((str.charAt(i) - '0') *
Math.pow(b, counter)));
counter--;
}
System.out.print(sum + " ");
// prev stores the previous decimal
int prev = sum;
// Computing decimal equivalents of all other windows
sum = 0; counter = 0;
for (; i < str.length(); i++)
{
// Subtracting weight of the element
// pushed out of window
sum = (int) (prev - ((str.charAt(i - k) - '0') *
Math.pow(b, k - 1)));
// Multiplying the decimal by base
// to formulate other window
sum = sum * b;
// Adding the new element of window to sum
sum = sum + (str.charAt(i) - '0');
// Decimal of current window
System.out.print(sum + " ");
// Updating prev
prev = sum;
counter++;
}
}
// Driver code
public static void main(String[] args)
{
String str = "12212";
int b = 3, k = 3;
substringConversions(str, b, k);
}
}
// This code is contributed by Rajput-Ji
Python3
# Simple Python3 program to convert all
# substrings from decimal to given base.
import math as mt
def substringConversions(str1, k, b):
for i in range(0, len(str1) - k + 1):
# Saving substring in sub
sub = str1[i:k + i]
# Evaluating decimal for current
# substring and printing it.
Sum = 0
counter = 0
for i in range(len(sub) - 1, -1, -1):
Sum = (Sum + ((ord(sub[i]) - ord('0')) *
pow(b, counter)))
counter += 1
print(Sum, end = " ")
# Driver code
str1 = "12212"
b = 3
k = 3
substringConversions(str1, b, k)
# This code is contributed by
# Mohit Kumar 29
C#
// Efficient C# program to convert
// all substrings from decimal to given base.
using System;
class GFG
{
static void substringConversions(String str,
int k, int b)
{
int i = 0, sum = 0, counter = k-1;
// Computing the decimal of first window
for (i = 0; i < k; i++)
{
sum = (int) (sum + ((str[i] - '0') *
Math.Pow(b, counter)));
counter--;
}
Console.Write(sum + " ");
// prev stores the previous decimal
int prev = sum;
// Computing decimal equivalents
// of all other windows
sum = 0; counter = 0;
for (; i < str.Length; i++)
{
// Subtracting weight of the element
// pushed out of window
sum = (int) (prev - ((str[i - k] - '0') *
Math.Pow(b, k - 1)));
// Multiplying the decimal by base
// to formulate other window
sum = sum * b;
// Adding the new element of window to sum
sum = sum + (str[i] - '0');
// Decimal of current window
Console.Write(sum + " ");
// Updating prev
prev = sum;
counter++;
}
}
// Driver code
public static void Main(String[] args)
{
String str = "12212";
int b = 3, k = 3;
substringConversions(str, b, k);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Efficient Javascript program to convert
// all substrings from decimal to given base.
function substringConversions(str, k, b)
{
let i = 0, sum = 0, counter = k-1;
// Computing the decimal of first window
for(i = 0; i < k; i++)
{
sum = (sum + ((str[i].charCodeAt(0) -
'0'.charCodeAt(0)) *
Math.pow(b, counter)));
counter--;
}
document.write(sum + " ");
// prev stores the previous decimal
let prev = sum;
// Computing decimal equivalents of
// all other windows
sum = 0; counter = 0;
for(; i < str.length; i++)
{
// Subtracting weight of the element
// pushed out of window
sum = (prev - ((str[i - k].charCodeAt(0) -
'0'.charCodeAt(0)) *
Math.pow(b, k - 1)));
// Multiplying the decimal by base
// to formulate other window
sum = sum * b;
// Adding the new element of window to sum
sum = sum + (str[i].charCodeAt(0) -
'0'.charCodeAt(0));
// Decimal of current window
document.write(sum + " ");
// Updating prev
prev = sum;
counter++;
}
}
// Driver code
let str = "12212";
let b = 3, k = 3;
substringConversions(str, b, k);
// This code is contributed by unknown2108
</script>
Producción
17 25 23
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi y Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA