fork download
copy 
  1. // A C++ program to check if a string is 'n' times 
  2. // repetition of one of its substrings 
  3. #include<bits/stdc++.h> 
  4. #include<cstring> 
  5. using namespace std; 
  6.  
  7. // A utility function to fill lps[] or compute prefix funcrion 
  8. // used in KMP string matching algorithm. Refer 
  9. // https://w...content-available-to-author-only...s.org/archives/11902 for details 
  10. void computeLPSArray(char str[], int M, int lps[]) 
  11. { 
  12. 	int len = 0; //lenght of the previous longest prefix suffix 
  13. 	int i; 
  14.  
  15. 	lps[0] = 0; //lps[0] is always 0 
  16. 	i = 1; 
  17.  
  18. 	// the loop calculates lps[i] for i = 1 to M-1 
  19. 	while (i < M) 
  20. 	{ 
  21. 	if (str[i] == str[len]) 
  22. 	{ 
  23. 		len++; 
  24. 		lps[i] = len; 
  25. 		i++; 
  26. 	} 
  27. 	else // (pat[i] != pat[len]) 
  28. 	{ 
  29. 		if (len != 0) 
  30. 		{ 
  31. 			// This is tricky. Consider the example AAACAAAA 
  32. 			// and i = 7. 
  33. 			len = lps[len-1]; 
  34.  
  35. 			// Also, note that we do not increment i here 
  36. 		} 
  37. 		else // if (len == 0) 
  38. 		{ 
  39. 			lps[i] = 0; 
  40. 			i++; 
  41. 		} 
  42. 	} 
  43. 	} 
  44. } 
  45.  
  46. // Returns true if str is repetition of one of its substrings 
  47. // else return false. 
  48. bool isRepeat(char str[]) 
  49. { 
  50. 	// Find length of string and create an array to 
  51. 	// store lps values used in KMP 
  52. 	int n = strlen(str); 
  53. 	int lps[n]; 
  54.  
  55. 	// Preprocess the pattern (calculate lps[] array) 
  56. 	computeLPSArray(str, n, lps); 
  57.  
  58. 	// Find length of longest suffix which is also 
  59. 	// prefix of str. 
  60. 	int len = lps[n-1]; 
  61. 	for(auto i=0;i<n;i++)
  62. 	cout<<lps[i]<<" ";
  63.   cout<<"len"<<len;
  64.  
  65. 	// If there exist a suffix which is also prefix AND 
  66. 	// Length of the remaining substring divides total 
  67. 	// length, then str[0..n-len-1] is the substring that 
  68. 	// repeats n/(n-len) times (Readers can print substring 
  69. 	// and value of n/(n-len) for more clarity. 
  70. 	return (len > 0 && n%(n-len) == 0)? true: false; 
  71. } 
  72.  
  73. // Driver program to test above function 
  74. int main() 
  75. { 
  76. char txt[][100] = {"ABCABC", "ABABAB", "ABCDABCD", "GEEKSFORGEEKS", 
  77. 					"GEEKGEEK", "AAAACAAAAC", "ABCDABC"}; 
  78. int n = sizeof(txt)/sizeof(txt[0]); 
  79. for (int i=0; i<n; i++) 
  80. 	isRepeat(txt[i])? cout << "True\n" : cout << "False\n"; 
  81. return 0; 
  82. } 
  83.  
Success #stdin #stdout 0s 4416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0 0 1 2 3 len3True
0 0 1 2 3 4 len4True
0 0 0 0 1 2 3 4 len4True
0 0 0 0 0 0 0 0 1 2 3 4 5 len5False
0 0 0 0 1 2 3 4 len4True
0 1 2 3 0 1 2 3 4 5 len5True
0 0 0 0 1 2 3 len3False
https://ideone.com/jbBoYo
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!