[UVA] 719 - Glass Beads

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 719 - Glass Beads
Source            : UVA Online Judge
Category          : String
Algorithm         : Lexicographically minimul string rotation by Zhou Yuan
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. int minExp(string s)  
6. {  
7.       s = s + s;  
8.       int i = 0;  
9.       int j = 1;  
10.       int k = 0;  
11.       int len = s.size();  
12.       while (i + k < len && j + k < len)  
13.       {  
14.           if (s[i+k] == s[j+k]) k++;  
15.           else if (s[i+k] < s[j+k])  
16.           {  
17.               j = j + k + 1;  
18.               if (j <= i) j = i + 1;  
19.               k = 0;  
20.           }  
21.           else  
22.           {  
23.               i = i + k + 1;  
24.               if (i <= j) i = j + 1;  
25.               k = 0;  
26.           }  
27.       }  
28.       return min(i, j);  
29. }  
30.   
31. int main()  
32. {  
33.       ios::sync_with_stdio(false);  
34.       cin.tie(nullptr);  
35.       cout.tie(nullptr);  
36.   
37.       int n;  
38.       cin >> n;  
39.       while (n--)  
40.       {  
41.           string s;  
42.           cin >> s;  
43.           int start = minExp(s);  
44.           cout << start+1 << endl;  
45.       }  
46. }