fork(18) download
copy 
  1. #include<stdio.h>
  2. #include<string.h>
  3. #define MAX 20011
  4.  
  5. char arr[MAX];
  6.  
  7. int BoothAlgo(){
  8.     int len = strlen(arr);
  9.     char lst[MAX];
  10.     strncpy(lst, arr, len);
  11.     strncpy(lst+len, arr, len);
  12. 	int ans, i, j;
  13. 	ans = 0;
  14. 	int f[2*len];
  15. 	for( i = 0; i < 2*len; ++i)
  16. 		f[i] = -1;
  17. 	for ( j = 1; j < 2*len; ++j) {
  18. 		i = f[j-ans-1];
  19. 		while( i != -1 && lst[j] != lst[ans+i+1]){
  20. 			if( lst[i] < lst[ans+i+1] )
  21. 				ans = j-i-1;
  22. 			i = f[i];
  23. 		}
  24. 		if( i == -1 && lst[j] != lst[ans+i+1] ){
  25. 			if( lst[j] < lst[ans+i+1] )
  26. 				ans = j;
  27. 			f[j-ans] = -1;
  28. 		}
  29. 		else
  30. 			f[j-ans] = i+1;
  31. 	}
  32.     return ans;
  33. }
  34.  
  35. int main(){
  36.     int c;
  37.     scanf("%d", &c);
  38.     while(c--){
  39.         scanf("%s", arr);
  40.         printf("%d\n", BoothAlgo()+1);
  41.     }
  42.     return 0;
  43. }
  44.  
  45.  
Success #stdin #stdout 0.01s 1696KB
comments (?)
stdin
copy 
2
helloworld
abbaa
stdout
copy 
10
4
https://ideone.com/J5gl5
language:
C (gcc 8.3)
created:
13 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!