Dada una string str y un entero K , la tarea es verificar si la string dada es K-periódica . Una string es k-periódica si la string es una repetición de la substring str[0 … k-1], es decir, la string “ababab” es 2-periódica . Imprima Sí si la string dada es k-periódica, de lo contrario imprima No.
Ejemplos:
Entrada: str = “geeksgeeks”, k = 5
Salida: Sí La
string dada se puede generar repitiendo el prefijo de longitud k, es decir, “geeks”Entrada: str = «geeksforgeeks», k = 3
Salida: No
Enfoque: comenzando con la substring str[k, 2k-1] , str[2k, 3k-1] y así sucesivamente, verifique si todas estas substrings son iguales al prefijo de la string de longitud k , es decir , str [0, k-1] . Si la condición es verdadera para todas esas substrings, imprima Sí ; de lo contrario, imprima No.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function that return true if sub-string
// of length k starting at index i is also
// a prefix of the string
bool isPrefix(string str, int len, int i, int k)
{
// k length sub-string cannot start at index i
if (i + k > len)
return false;
for (int j = 0; j < k; j++)
{
// Character mismatch between the prefix
// and the sub-string starting at index i
if (str[i] != str[j])
return false;
i++;
}
return true;
}
// Function that returns true if str is K-periodic
bool isKPeriodic(string str, int len, int k)
{
// Check whether all the sub-strings
// str[0, k-1], str[k, 2k-1] ... are equal
// to the k length prefix of the string
for (int i = k; i < len; i += k)
if (!isPrefix(str, len, i, k))
return false;
return true;
}
// Driver code
int main()
{
string str = "geeksgeeks";
int len = str.length();
int k = 5;
if (isKPeriodic(str, len, k))
cout << ("Yes");
else
cout << ("No");
}
// This code is contributed by
// Surendra_Gangwar
Java
// Java implementation of the approach
class GFG {
// Function that return true if sub-string
// of length k starting at index i is also
// a prefix of the string
static boolean isPrefix(String str, int len, int i, int k)
{
// k length sub-string cannot start at index i
if (i + k > len)
return false;
for (int j = 0; j < k; j++) {
// Character mismatch between the prefix
// and the sub-string starting at index i
if (str.charAt(i) != str.charAt(j))
return false;
i++;
}
return true;
}
// Function that returns true if str is K-periodic
static boolean isKPeriodic(String str, int len, int k)
{
// Check whether all the sub-strings
// str[0, k-1], str[k, 2k-1] ... are equal
// to the k length prefix of the string
for (int i = k; i < len; i += k)
if (!isPrefix(str, len, i, k))
return false;
return true;
}
// Driver code
public static void main(String[] args)
{
String str = "geeksgeeks";
int len = str.length();
int k = 5;
if (isKPeriodic(str, len, k))
System.out.print("Yes");
else
System.out.print("No");
}
}
Python3
# Python3 implementation of the approach
# Function that returns true if sub-string
# of length k starting at index i
# is also a prefix of the string
def isPrefix(string, length, i, k):
# k length sub-string cannot
# start at index i
if i + k > length:
return False
for j in range(0, k):
# Character mismatch between the prefix
# and the sub-string starting at index i
if string[i] != string[j]:
return False
i += 1
return True
# Function that returns true if
# str is K-periodic
def isKPeriodic(string, length, k):
# Check whether all the sub-strings
# str[0, k-1], str[k, 2k-1] ... are equal
# to the k length prefix of the string
for i in range(k, length, k):
if isPrefix(string, length, i, k) == False:
return False
return True
# Driver code
if __name__ == "__main__":
string = "geeksgeeks"
length = len(string)
k = 5
if isKPeriodic(string, length, k) == True:
print("Yes")
else:
print("No")
# This code is contributed
# by Rituraj Jain
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that return true if sub-string
// of length k starting at index i is also
// a prefix of the string
static bool isPrefix(String str, int len, int i, int k)
{
// k length sub-string cannot start at index i
if (i + k > len)
return false;
for (int j = 0; j < k; j++)
{
// Character mismatch between the prefix
// and the sub-string starting at index i
if (str[i] != str[j])
return false;
i++;
}
return true;
}
// Function that returns true if str is K-periodic
static bool isKPeriodic(String str, int len, int k)
{
// Check whether all the sub-strings
// str[0, k-1], str[k, 2k-1] ... are equal
// to the k length prefix of the string
for (int i = k; i < len; i += k)
if (!isPrefix(str, len, i, k))
return false;
return true;
}
// Driver code
public static void Main()
{
String str = "geeksgeeks";
int len = str.Length;
int k = 5;
if (isKPeriodic(str, len, k))
Console.Write("Yes");
else
Console.Write("No");
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP implementation of the approach
// Function that return true if sub-
// of length $k starting at index $i
// is also a prefix of the string
function isPrefix($str, $len, $i, $k)
{
// $k length sub- cannot start at index $i
if ($i + $k > $len)
return false;
for ( $j = 0; $j < $k; $j++)
{
// Character mismatch between the prefix
// and the sub- starting at index $i
if ($str[$i] != $str[$j])
return false;
$i++;
}
return true;
}
// Function that returns true if $str is K-periodic
function isKPeriodic($str, $len, $k)
{
// Check whether all the sub-strings
// $str[0, $k-1], $str[$k, 2k-1] ... are equal
// to the $k length prefix of the
for ($i = $k; $i < $len; $i += $k)
if (!isPrefix($str, $len, $i, $k))
return false;
return true;
}
// Driver code
$str = "geeksgeeks";
$len = strlen($str);
$k = 5;
if (isKPeriodic($str, $len, $k))
echo ("Yes");
else
echo ("No");
// This code is contributed by ihritik
?>
Javascript
<script>
// js implementation of the approach
// Function that return true if sub-string
// of length k starting at index i is also
// a prefix of the string
function isPrefix(str, len, i, k){
// k length sub-string cannot start at index i
if (i + k > len)
return false;
for (let j = 0; j < k; j++)
{
// Character mismatch between the prefix
// and the sub-string starting at index i
if (str[i] != str[j])
return false;
i++;
}
return true;
}
// Function that returns true if str is K-periodic
function isKPeriodic(str, len, k)
{
// Check whether all the sub-strings
// str[0, k-1], str[k, 2k-1] ... are equal
// to the k length prefix of the string
for (let i = k; i < len; i += k)
if (!isPrefix(str, len, i, k))
return false;
return true;
}
// Driver code
let str = "geeksgeeks";
let len = str.length;
let k = 5;
if (isKPeriodic(str, len, k))
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad de tiempo: O(K * log(len))
Espacio auxiliar: O(1)
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