给定一个字符串“str”，检查它是否可以通过获取该字符串的一个子字符串并将该子字符串的多个副本附加在一起来构造。
null
例如：
Input: str = "abcabcabc"Output: trueThe given string is 3 times repetition of "abc"Input: str = "abadabad"Output: trueThe given string is 2 times repetition of "abad"Input: str = "aabaabaabaab"Output: trueThe given string is 4 times repetition of "aab"Input: str = "abcdabc"Output: false
资料来源： 谷歌面试问题
我们强烈建议您在继续解决方案之前单击此处并进行练习。
这个问题有很多解决方案。最具挑战性的部分是在O（n）时间内解决问题。下面是一个O（n）算法。
设给定字符串为’str’，给定字符串的长度为’n’。 1） 查找“str”的最长正确前缀的长度，该前缀也是后缀。让最长的正确前缀后缀的长度为’len’。这可以使用以下预处理步骤在O（n）时间内计算： KMP字符串匹配算法 . 2） 如果“n–len”的值除以n（或“n%（n-len）”，则返回true，否则返回false。 在“true”的情况下，子字符串“str[0..n-len-1]”是重复n/（n-len）次的子字符串。
让我们举几个例子。 输入：str=“ABCDABCD”，n=8（str”中的字符数） len的值是4（“ABCD”是最长的子串，它既是前缀又是后缀） 因为（n-len）除以n，所以答案是正确的。 输入：str=“ABCDABC”，n=7（str”中的字符数） len的值是3（“ABC”是最长的子串，它既是前缀又是后缀） 因为（n-len）不除以n，所以答案是错的。 输入：str=“abcabc”，n=15（str中的字符数） len的值是12（“abcabc”是最长的子串，它既是前缀又是后缀） 因为（n-len）除以n，所以答案是正确的。
这是怎么回事？ 最长正确前缀后缀（或len）的长度始终在0到n-1之间。如果len是n-1，那么字符串中的所有字符都是相同的。例如，len的“AAAA”是3。如果len为n-2且n为偶数，则字符串中的两个字符重复n/2次。例如“ABABABAB”，lps的长度为6。原因是，如果前n-2个字符与最后n-2个字符相同，则从第一对开始，每对字符都与下一对相同。下图显示了长度为4的子字符串的相同情况。
以下是上述算法的实现：
C++
// A C++ program to check if a string is 'n' times // repetition of one of its substrings #include<iostream> #include<cstring> using namespace std; // A utility function to fill lps[] or compute prefix function // used in KMP string matching algorithm. Refer // https://www.geeksforgeeks.org/archives/11902 for details void computeLPSArray( char str[], int M, int lps[]) { int len = 0; //length of the previous longest prefix suffix int i; lps[0] = 0; //lps[0] is always 0 i = 1; // the loop calculates lps[i] for i = 1 to M-1 while (i < M) { if (str[i] == str[len]) { len++; lps[i] = len; i++; } else // (pat[i] != pat[len]) { if (len != 0) { // This is tricky. Consider the example AAACAAAA // and i = 7. len = lps[len-1]; // Also, note that we do not increment i here } else // if (len == 0) { lps[i] = 0; i++; } } } } // Returns true if str is repetition of one of its substrings // else return false. bool isRepeat( char str[]) { // Find length of string and create an array to // store lps values used in KMP int n = strlen (str); int lps[n]; // Preprocess the pattern (calculate lps[] array) computeLPSArray(str, n, lps); // Find length of longest suffix which is also // prefix of str. int len = lps[n-1]; // If there exist a suffix which is also prefix AND // Length of the remaining substring divides total // length, then str[0..n-len-1] is the substring that // repeats n/(n-len) times (Readers can print substring // and value of n/(n-len) for more clarity. return (len > 0 && n%(n-len) == 0)? true : false ; } // Driver program to test above function int main() { char txt[][100] = { "ABCABC" , "ABABAB" , "ABCDABCD" , "GEEKSFORGEEKS" , "GEEKGEEK" , "AAAACAAAAC" , "ABCDABC" }; int n = sizeof (txt)/ sizeof (txt[0]); for ( int i=0; i<n; i++) isRepeat(txt[i])? cout << "True" : cout << "False" ; return 0; } |
JAVA
// Java program to check if a string is 'n' // times repetition of one of its substrings import java.io.*; class GFG { // A utility function to fill lps[] or compute // prefix function used in KMP string matching // algorithm. Refer // for details static void computeLPSArray(String str, int M, int lps[]) { // length of the previous // longest prefix suffix int len = 0 ; int i; lps[ 0 ] = 0 ; // lps[0] is always 0 i = 1 ; // the loop calculates lps[i] // for i = 1 to M-1 while (i < M) { if (str.charAt(i) == str.charAt(len)) { len++; lps[i] = len; i++; } else // (pat[i] != pat[len]) { if (len != 0 ) { // This is tricky. Consider the // example AAACAAAA and i = 7. len = lps[len- 1 ]; // Also, note that we do // not increment i here } else // if (len == 0) { lps[i] = 0 ; i++; } } } } // Returns true if str is repetition of // one of its substrings else return false. static boolean isRepeat(String str) { // Find length of string and create // an array to store lps values used in KMP int n = str.length(); int lps[] = new int [n]; // Preprocess the pattern (calculate lps[] array) computeLPSArray(str, n, lps); // Find length of longest suffix // which is also prefix of str. int len = lps[n- 1 ]; // If there exist a suffix which is also // prefix AND Length of the remaining substring // divides total length, then str[0..n-len-1] // is the substring that repeats n/(n-len) // times (Readers can print substring and // value of n/(n-len) for more clarity. return (len > 0 && n%(n-len) == 0 )? true : false ; } // Driver program to test above function public static void main(String[] args) { String txt[] = { "ABCABC" , "ABABAB" , "ABCDABCD" , "GEEKSFORGEEKS" , "GEEKGEEK" , "AAAACAAAAC" , "ABCDABC" }; int n = txt.length; for ( int i = 0 ; i < n; i++) { if (isRepeat(txt[i]) == true ) System.out.println( "True" ); else System.out.println( "False" ); } } } // This code is contributed by Prerna Saini |
Python3
# A Python program to check if a string is 'n' times # repetition of one of its substrings # A utility function to fill lps[] or compute prefix function # used in KMP string matching algorithm. Refer # https://www.geeksforgeeks.org/archives/11902 for details def computeLPSArray(string, M, lps): length = 0 # length of the previous longest prefix suffix i = 1 lps[ 0 ] = 0 # lps[0] is always 0 # the loop calculates lps[i] for i = 1 to M-1 while i < M: if string[i] = = string[length]: length + = 1 lps[i] = length i + = 1 else : if length ! = 0 : # This is tricky. Consider the example AAACAAAA # and i = 7. length = lps[length - 1 ] # Also, note that we do not increment i here else : lps[i] = 0 i + = 1 # Returns true if string is repetition of one of its substrings # else return false. def isRepeat(string): # Find length of string and create an array to # store lps values used in KMP n = len (string) lps = [ 0 ] * n # Preprocess the pattern (calculate lps[] array) computeLPSArray(string, n, lps) # Find length of longest suffix which is also # prefix of str. length = lps[n - 1 ] # If there exist a suffix which is also prefix AND # Length of the remaining substring divides total # length, then str[0..n-len-1] is the substring that # repeats n/(n-len) times (Readers can print substring # and value of n/(n-len) for more clarity. if length > 0 and n % (n - length) = = 0 : return True else : False # Driver program txt = [ "ABCABC" , "ABABAB" , "ABCDABCD" , "GEEKSFORGEEKS" , "GEEKGEEK" , "AAAACAAAAC" , "ABCDABC" ] n = len (txt) for i in range (n): if isRepeat(txt[i]): print ( True ) else : print ( False ) # This code is contributed by BHAVYA JAIN |
C#
// C# program to check if a string is 'n' // times repetition of one of its substrings using System; class GFG { // A utility function to fill lps[] or // compute prefix function used in KMP // string matching algorithm. Refer // for details static void computeLPSArray(String str, int M, int []lps) { // length of the previous // longest prefix suffix int len = 0; int i; lps[0] = 0; // lps[0] is always 0 i = 1; // the loop calculates lps[i] // for i = 1 to M-1 while (i < M) { if (str[i] == str[len]) { len++; lps[i] = len; i++; } else // (pat[i] != pat[len]) { if (len != 0) { // This is tricky. Consider the // example AAACAAAA and i = 7. len = lps[len-1]; // Also, note that we do // not increment i here } else // if (len == 0) { lps[i] = 0; i++; } } } } // Returns true if str is repetition of // one of its substrings else return false. static bool isRepeat(String str) { // Find length of string and create // an array to store lps values used // in KMP int n = str.Length; int [] lps = new int [n]; // Preprocess the pattern (calculate // lps[] array) computeLPSArray(str, n, lps); // Find length of longest suffix // which is also prefix of str. int len = lps[n-1]; // If there exist a suffix which is also // prefix AND Length of the remaining // substring divides total length, then // str[0..n-len-1] is the substring that // repeats n/(n-len) times (Readers can // print substring and value of n/(n-len) // for more clarity. return (len > 0 && n % (n - len) == 0) ? true : false ; } // Driver program to test above function public static void Main() { String[] txt = { "ABCABC" , "ABABAB" , "ABCDABCD" , "GEEKSFORGEEKS" , "GEEKGEEK" , "AAAACAAAAC" , "ABCDABC" }; int n = txt.Length; for ( int i = 0; i < n; i++) { if (isRepeat(txt[i]) == true ) Console.WriteLine( "True" ); else Console.WriteLine( "False" ); } } } // This code is contributed by Sam007. |
Javascript
<script> // Javascript program to check if a string is 'n' // times repetition of one of its substrings // A utility function to fill lps[] or // compute prefix function used in KMP // string matching algorithm. Refer // for details function computeLPSArray(str, M, lps) { // length of the previous // longest prefix suffix let len = 0; let i; lps[0] = 0; // lps[0] is always 0 i = 1; // the loop calculates lps[i] // for i = 1 to M-1 while (i < M) { if (str[i] == str[len]) { len++; lps[i] = len; i++; } else // (pat[i] != pat[len]) { if (len != 0) { // This is tricky. Consider the // example AAACAAAA and i = 7. len = lps[len-1]; // Also, note that we do // not increment i here } else // if (len == 0) { lps[i] = 0; i++; } } } } // Returns true if str is repetition of // one of its substrings else return false. function isRepeat(str) { // Find length of string and create // an array to store lps values used // in KMP let n = str.length; let lps = new Array(n); lps.fill(0); // Preprocess the pattern (calculate // lps[] array) computeLPSArray(str, n, lps); // Find length of longest suffix // which is also prefix of str. let len = lps[n-1]; // If there exist a suffix which is also // prefix AND Length of the remaining // substring divides total length, then // str[0..n-len-1] is the substring that // repeats n/(n-len) times (Readers can // print substring and value of n/(n-len) // for more clarity. return (len > 0 && n % (n - len) == 0) ? true : false ; } let txt = [ "ABCABC" , "ABABAB" , "ABCDABCD" , "GEEKSFORGEEKS" , "GEEKGEEK" , "AAAACAAAAC" , "ABCDABC" ]; let n = txt.length; for (let i = 0; i < n; i++) { if (isRepeat(txt[i]) == true ) document.write( "True" + "</br>" ); else document.write( "False" + "</br>" ); } </script> |
输出：
TrueTrueTrueFalseTrueTrueFalse
时间复杂度：上述解决方案的时间复杂度为O（n） KMP预处理算法 这是线性时间算法。
本文由 哈希特·阿格拉瓦尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
