Longest K-Repeated Substring
In many data compression algorithms, pattern matching, and bioinformatics applications, identifying repetitive structures within sequences is crucial. This problem focuses on finding the most significant repetitive pattern in a given text: the longest substring that can be formed by concatenating a smaller, non-empty pattern string P at least k times. This task requires efficient string processing and pattern recognition, essential skills for optimizing data handling in high-performance computing environments.
Your task is to implement a function findLongestKRepeatedSubstring that takes a string text and an integer k as input. The function should identify the longest substring S' of text such that S' can be expressed as P concatenated m times (P^m), where P is a non-empty string and m >= k.
If there are multiple such substrings with the same maximum length, you should return the one that appears earliest (has the smallest starting index) in the text.
If no such substring exists (e.g., text = "abc", k = 2), return an empty string.
text: A string consisting of lowercase English letters.k: An integer representing the minimum number of repetitions for the pattern P.k-repeated substring found according to the rules above. If no such substring exists, return an empty string.S' is considered P^m if S' is formed by repeating the non-empty string P exactly m times. For example, "abcabc" is "abc" repeated 2 times.P must be non-empty.k=1, any substring is P^1. The problem then asks for the longest substring, which would be the entire text.Examples
Example 1
Input:
text = "abcabcabc", k = 2
Output:
"abcabcabc"
Note:
The substring "abcabcabc" can be formed by repeating "abc" 3 times. Since 3 >= k (2), and it's the longest such substring, it's the answer.
Example 2
Input:
text = "ababa", k = 2
Output:
"abab"
Note:
The substring "abab" (starting at index 0) can be formed by repeating "ab" 2 times. Its length is 4. The substring "baba" (starting at index 1) can be formed by repeating "ba" 2 times. Its length is also 4. Since "abab" appears earlier in the text (index 0 < index 1), it is the preferred answer.
Example 3
Input:
text = "banana", k = 3
Output:
""
Note:
No substring can be formed by repeating a pattern P 3 or more times. For example, "nana" is "na" repeated twice, but 2 < k (3).
Constraints
1 <= text.length <= 20001 <= k <= text.lengthtext consists only of lowercase English letters ('a' through 'z').text.length = 2000 within typical time limits (e.g., a few seconds).k-repeated substring, handling ties by earliest occurrence, and edge cases.Loading editor...