Given a string str of size N, the task is to check whether the given string is K-periodic, for all Ks in range [1, N]. Print Yes if the given string is K-periodic, else print No.
A string is K-periodic, if the string is a repetition of the sub-string str[0 … k-1].
For example, the string “ababab” is 2-periodic.
Examples:
Input: N = 7, S = “abcabca”
Output: 3 6 7
Explanation:
1. Consider prefix of length 1 (i.e. “a”), then if we repeat this prefix to make a string of length 7, we get “aaaaaaa” which is not equal to the original string.
2. Consider prefix of length 2 (i.e. “ab”), then if we repeat this prefix to make a string of length 7, we get “abababa” which is not equal to the original string.
3. Consider prefix of length 3 (i.e. “abc”), then if we repeat this prefix to make a string of length 7, we get “abcabca” which is equal to the original string.
4. Consider prefix of length 4 (i.e. “abca”), then if we repeat this prefix to make a string of length 7, we get “abcaabc” which is not equal to the original string.
5. Consider prefix of length 5 (i.e. “abcab”), then if we repeat this prefix to make a string of length 7, we get “abcabab” which is not equal to the original string.
6. Consider prefix of length 6 (i.e. “abcabc”), then if we repeat this prefix to make a string of length 7, we get “abcabca” which is equal to the original string.
7. Consider prefix of length 7 (i.e. “abcabca”), then if we repeat this prefix to make a string of length 7, we get “abcabca” which is equal to the original string.Input: N = 5, S = “aaaaa”
Output: 1 2 3 4 5
Explanation: As all the characters of the given string are same hence, the string can be generated by repeating the prefix of length 1 to N.
Approach: The task can be solved using z-algorithm.
- Let’s construct Z array for the given string. (0-indexed)
- Then, i to be a period, (N-i) should be equal to the z value at index i, because if ‘i’ is one of the period of the string, then a suffix of length (N-i) exactly matches with prefix of length (n-i).
- At last, append N (length of the string) to the answer, the N value is trivial which the above mentioned method doesn’t find.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <iostream>using namespace std;void getZarr(string str, int Z[]);// Prints all the period of a stringvoid findPeriod(string text){ int l = text.length(); // Construct Z array int Z[l]; getZarr(text, Z); // Now looping through Z array // For finding period for (int i = 1; i < l; ++i) { // If(l-i) is equal to Z[i], // Then one of the period // Of string is i if (Z[i] == (l - i)) cout << i << " "; } // Print trivial value //(i.e. length of string) cout << l << endl;}// Fills Z array for given string str[]void getZarr(string str, int Z[]){ int n = str.length(); int L, R, k; // [L, R] make a window // Which matches with prefix of s L = R = 0; for (int i = 1; i < n; ++i) { // If i>R nothing matches // So we will calculate. // Z[i] using naive way. if (i > R) { L = R = i; // R-L = 0 in starting, so it will start // Checking from 0'th index. For example, // For "ababab" and i = 1, the value of R // Remains 0 and Z[i] becomes 0. For string // "aaaaaa" and i = 1, Z[i] and R become 5 while (R < n && str[R - L] == str[R]) R++; Z[i] = R - L; R--; } else { // k = i-L so k corresponds to number // Which matches in [L, R] interval. k = i - L; // If Z[k] is less than remaining interval // Then Z[i] will be equal to Z[k]. // For example, str = "ababab", i = 3, R = 5 // and L = 2 if (Z[k] < R - i + 1) Z[i] = Z[k]; // For example str = "aaaaaa" // and i = 2, R is 5, L is 0 else { // Else start from R // And check manually L = i; while (R < n && str[R - L] == str[R]) R++; Z[i] = R - L; R--; } } }}// Driver codeint main(){ string text = "abcabca"; findPeriod(text); return 0;} |
Java
// A Java program that implements Z algorithm for period// findingclass GFG { // prints all the period of string public static void findPeriod(String text) { int l = text.length(); int Z[] = new int[l]; // Construct Z array getZarr(text, Z); // now looping through Z array for finding period for (int i = 0; i < l; ++i) { // if Z[i] is equal to (l-i), then one // of the period of string is i if (Z[i] == (l - i)) { System.out.print(i + " "); } } // Print trivial value (i.e. length of string) System.out.println(l); } // Fills Z array for given string str[] private static void getZarr(String str, int[] Z) { int n = str.length(); // [L, R] make a window which matches with // prefix of s int L = 0, R = 0; for (int i = 1; i < n; ++i) { // if i>R nothing matches so we will calculate. // Z[i] using naive way. if (i > R) { L = R = i; // R-L = 0 in starting, so it will start // checking from 0'th index. For example, // for "ababab" and i = 1, the value of R // remains 0 and Z[i] becomes 0. For string // "aaaaaa" and i = 1, Z[i] and R become 5 while (R < n && str.charAt(R - L) == str.charAt(R)) R++; Z[i] = R - L; R--; } else { // k = i-L so k corresponds to number which // matches in [L, R] interval. int k = i - L; // if Z[k] is less than remaining interval // then Z[i] will be equal to Z[k]. // For example, str = "ababab", i = 3, R = 5 // and L = 2 if (Z[k] < R - i + 1) Z[i] = Z[k]; // For example str = "aaaaaa" and i = 2, R is 5, // L is 0 else { // else start from R and check manually L = i; while (R < n && str.charAt(R - L) == str.charAt(R)) R++; Z[i] = R - L; R--; } } } } // Driver program public static void main(String[] args) { String text = "abcabca"; findPeriod(text); }} |
Python3
# python3 code for the above approach:# Fills Z array for given string str[]def getZarr(str, Z): n = len(str) L, R, k = 0, 0, 0 # [L, R] make a window # Which matches with prefix of s for i in range(1, n): # If i>R nothing matches # So we will calculate. # Z[i] using naive way. if (i > R): L = R = i # R-L = 0 in starting, so it will start # Checking from 0'th index. For example, # For "ababab" and i = 1, the value of R # Remains 0 and Z[i] becomes 0. For string # "aaaaaa" and i = 1, Z[i] and R become 5 while (R < n and str[R - L] == str[R]): R += 1 Z[i] = R - L R -= 1 else: # k = i-L so k corresponds to number # Which matches in [L, R] interval. k = i - L # If Z[k] is less than remaining interval # Then Z[i] will be equal to Z[k]. # For example, str = "ababab", i = 3, R = 5 # and L = 2 if (Z[k] < R - i + 1): Z[i] = Z[k] # For example str = "aaaaaa" # and i = 2, R is 5, L is 0 else: # Else start from R # And check manually L = i while (R < n and str[R - L] == str[R]): R += 1 Z[i] = R - L R -= 1# Prints all the period of a stringdef findPeriod(text): l = len(text) # Construct Z array Z = [0 for _ in range(l)] getZarr(text, Z) # Now looping through Z array # For finding period for i in range(1, l): # If(l-i) is equal to Z[i], # Then one of the period # Of string is i if (Z[i] == (l - i)): print(i, end=" ") # Print trivial value # (i.e. length of string) print(l)# Driver codeif __name__ == "__main__": text = "abcabca" findPeriod(text)# This code is contributed by rakeshsahni |
C#
// C# code for the above approach:using System;class GFG { // Prints all the period of a string static void findPeriod(string text) { int l = text.Length; // Construct Z array int[] Z = new int[l]; getZarr(text, Z); // Now looping through Z array // For finding period for (int i = 1; i < l; ++i) { // If(l-i) is equal to Z[i], // Then one of the period // Of string is i if (Z[i] == (l - i)) Console.Write(i + " "); } // Print trivial value //(i.e. length of string) Console.WriteLine(l); } // Fills Z array for given string str[] static void getZarr(string str, int[] Z) { int n = str.Length; int L, R, k; // [L, R] make a window // Which matches with prefix of s L = R = 0; for (int i = 1; i < n; ++i) { // If i>R nothing matches // So we will calculate. // Z[i] using naive way. if (i > R) { L = R = i; // R-L = 0 in starting, so it will start // Checking from 0'th index. For example, // For "ababab" and i = 1, the value of R // Remains 0 and Z[i] becomes 0. For string // "aaaaaa" and i = 1, Z[i] and R become 5 while (R < n && str[R - L] == str[R]) R++; Z[i] = R - L; R--; } else { // k = i-L so k corresponds to number // Which matches in [L, R] interval. k = i - L; // If Z[k] is less than remaining interval // Then Z[i] will be equal to Z[k]. // For example, str = "ababab", i = 3, R = 5 // and L = 2 if (Z[k] < R - i + 1) Z[i] = Z[k]; // For example str = "aaaaaa" // and i = 2, R is 5, L is 0 else { // Else start from R // And check manually L = i; while (R < n && str[R - L] == str[R]) R++; Z[i] = R - L; R--; } } } } // Driver code public static int Main() { string text = "abcabca"; findPeriod(text); return 0; }}// This code is contributed by Taranpreet |
Javascript
<script> // JavaScript code for the above approach// Fills Z array for given string str[]function getZarr(str, Z){ let n = str.length; let L, R, k; // [L, R] make a window // Which matches with prefix of s L = R = 0; for (let i = 1; i < n; ++i) { // If i>R nothing matches // So we will calculate. // Z[i] using naive way. if (i > R) { L = R = i; // R-L = 0 in starting, so it will start // Checking from 0'th index. For example, // For "ababab" and i = 1, the value of R // Remains 0 and Z[i] becomes 0. For string // "aaaaaa" and i = 1, Z[i] and R become 5 while (R < n && str[R - L] == str[R]) R++; Z[i] = R - L; R--; } else { // k = i-L so k corresponds to number // Which matches in [L, R] interval. k = i - L; // If Z[k] is less than remaining interval // Then Z[i] will be equal to Z[k]. // For example, str = "ababab", i = 3, R = 5 // and L = 2 if (Z[k] < R - i + 1) Z[i] = Z[k]; // For example str = "aaaaaa" // and i = 2, R is 5, L is 0 else { // Else start from R // And check manually L = i; while (R < n && str[R - L] == str[R]) R++; Z[i] = R - L; R--; } } }}// Prints all the period of a stringfunction findPeriod(text){ let l = text.length; // Construct Z array let Z= new Array(l); getZarr(text, Z); // Now looping through Z array // For finding period for (let i = 1; i < l; ++i) { // If(l-i) is equal to Z[i], // Then one of the period // Of string is i if (Z[i] == (l - i)) document.write(i + " ") } // Print trivial value //(i.e. length of string) document.write(l + '<br>')}// Driver code let text = "abcabca"; findPeriod(text); // This code is contributed by Potta Lokesh </script> |
Output
3 6 7
Time complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
