Check if the given string is K-periodic
Last Updated :
02 Aug, 2021
Given a string str and an integer K, the task is to check whether the given string is K-periodic. A string is k-periodic if the string is a repetition of the sub-string str[0 … k-1] i.e. the string “ababab” is 2-periodic. Print Yes if the given string is k-periodic, else print No.
Examples:
Input: str = “geeksgeeks”, k = 5
Output: Yes
Given string can be generated by repeating the prefix of length k i.e. “geeks”
Input: str = “geeksforgeeks”, k = 3
Output: No
Approach: Starting with the sub-string str[k, 2k-1], str[2k, 3k-1] and so on, check whether all of these sub-strings are equal to the prefix of the string of length k i.e. str[0, k-1]. If the condition is true for all such sub-strings, then print Yes else print No.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>
using namespace std;
bool isPrefix(string str, int len, int i, int k)
{
if (i + k > len)
return false;
for (int j = 0; j < k; j++)
{
if (str[i] != str[j])
return false;
i++;
}
return true;
}
bool isKPeriodic(string str, int len, int k)
{
for (int i = k; i < len; i += k)
if (!isPrefix(str, len, i, k))
return false;
return true;
}
int main()
{
string str = "geeksgeeks";
int len = str.length();
int k = 5;
if (isKPeriodic(str, len, k))
cout << ("Yes");
else
cout << ("No");
}
|
Java
class GFG {
static boolean isPrefix(String str, int len, int i, int k)
{
if (i + k > len)
return false;
for (int j = 0; j < k; j++) {
if (str.charAt(i) != str.charAt(j))
return false;
i++;
}
return true;
}
static boolean isKPeriodic(String str, int len, int k)
{
for (int i = k; i < len; i += k)
if (!isPrefix(str, len, i, k))
return false;
return true;
}
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
def isPrefix(string, length, i, k):
if i + k > length:
return False
for j in range(0, k):
if string[i] != string[j]:
return False
i += 1
return True
def isKPeriodic(string, length, k):
for i in range(k, length, k):
if isPrefix(string, length, i, k) == False:
return False
return True
if __name__ == "__main__":
string = "geeksgeeks"
length = len(string)
k = 5
if isKPeriodic(string, length, k) == True:
print("Yes")
else:
print("No")
|
C#
using System;
class GFG
{
static bool isPrefix(String str, int len, int i, int k)
{
if (i + k > len)
return false;
for (int j = 0; j < k; j++)
{
if (str[i] != str[j])
return false;
i++;
}
return true;
}
static bool isKPeriodic(String str, int len, int k)
{
for (int i = k; i < len; i += k)
if (!isPrefix(str, len, i, k))
return false;
return true;
}
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");
}
}
|
PHP
<?php
function isPrefix($str, $len, $i, $k)
{
if ($i + $k > $len)
return false;
for ( $j = 0; $j < $k; $j++)
{
if ($str[$i] != $str[$j])
return false;
$i++;
}
return true;
}
function isKPeriodic($str, $len, $k)
{
for ($i = $k; $i < $len; $i += $k)
if (!isPrefix($str, $len, $i, $k))
return false;
return true;
}
$str = "geeksgeeks";
$len = strlen($str);
$k = 5;
if (isKPeriodic($str, $len, $k))
echo ("Yes");
else
echo ("No");
?>
|
Javascript
<script>
function isPrefix(str, len, i, k){
if (i + k > len)
return false;
for (let j = 0; j < k; j++)
{
if (str[i] != str[j])
return false;
i++;
}
return true;
}
function isKPeriodic(str, len, k)
{
for (let i = k; i < len; i += k)
if (!isPrefix(str, len, i, k))
return false;
return true;
}
let str = "geeksgeeks";
let len = str.length;
let k = 5;
if (isKPeriodic(str, len, k))
document.write("Yes");
else
document.write("No");
</script>
|
Time Complexity: O(K * log(len))
Auxiliary Space: O(1)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...