Compruebe si la string dada es K-periódica

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 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 ; 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

Deja una respuesta

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