Hidden PasswordACM South Eastern Europe -- 2003
Sometimes the programmers have very strange ways of hiding their passwords. Billy "Hacker" Geits chooses a string S composed of L (5 <= L <= 100,000) lowercase letters ('a'..'z') with length L. Then he makes and sorts all L-1 one-letter left cyclic shifts of the string. He then takes as a password one prefix of the lexicographically first of the obtained strings (including S).
For example consider the string "alabala". The sorted cyclic one-letter left shifts (including the initial string) are:

aalabal 
abalaal 
alaalab 
alabala 
balaala 
laalaba 
labalaa
Lexicographically, first string is 'aalabal'. The first letter of this string ('a') is the 'a' that was in position 6 in the initial string (counting the first letter in the string as position 0).
Write a program that, for given string S, finds the start position of the first letter of the sorted list of cyclic shifts of the string. If the first element appears more than once in the sorted list, then the program should output the smallest possible initial position.
PROGRAM NAME: hidden
INPUT FORMAT
Line 1: A single integer: L
Line 2..?: All L characters of the the string S, broken across lines such that each line has 72 characters except the last one, which might have fewer.
SAMPLE INPUT (file hidden.in)
7
alabala
OUTPUT FORMAT

    
Line 1: A single integer that is the start position of the first letter, as described above.

SAMPLE OUTPUT (file hidden.out)
6

USER: wang yucao [wangyuc2]
TASK: hidden
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4016 KB]
   Test 2: TEST OK [0.011 secs, 4016 KB]
   Test 3: TEST OK [0.011 secs, 4012 KB]
   Test 4: TEST OK [0.011 secs, 4012 KB]
   Test 5: TEST OK [0.000 secs, 4012 KB]
   Test 6: TEST OK [0.011 secs, 4016 KB]
   Test 7: TEST OK [0.011 secs, 4016 KB]
   Test 8: TEST OK [0.065 secs, 4012 KB]
   Test 9: TEST OK [0.065 secs, 4016 KB]
   Test 10: TEST OK [0.076 secs, 4016 KB]
   Test 11: TEST OK [0.065 secs, 4012 KB]
   Test 12: TEST OK [0.000 secs, 4012 KB]
   Test 13: TEST OK [0.022 secs, 4012 KB]
   Test 14: TEST OK [0.011 secs, 4012 KB]

All tests OK.
Your program ('hidden') produced all correct answers!  This is your
submission #5 for this problem.  Congratulations!
 
/*
PROB: hidden
LANG: C++
*/
/*
这道题事实上还是搜索，不过在过程中采用类似KMP中的思想，串是环形的，我们可以把串拷贝一遍放在后面。
然后，用st记录当前的起始位置，用maxn来记录最小串的起始位置，那么每次对比s[st+i]和s[maxn+i]
这样有三种情况：
1.s[maxn+i] < s[st+i]，这表示之前记录的最小串小于当前位置的串，结束；
2.s[maxn+i] == s[st+i]， 表示这个字符位相等，那么i后移一位；
3.s[maxn+i] > s[st+i]，这表示当前位置的字符串较小，应该更新最小串起始记录maxn为st，结束。
执行这个比较过程知道st>=n
在这个过程中，如果出现情况1，那么这次退出后i表示这两个串的相同前缀数，st可以直接加上i；
特别注意，如果在比较过程中，i==n了，那表示有两个串是相同的，这样要直接退出，输出0，否则test11超时！
*/
#include<iostream>
#include<fstream>
#include<cstring>
#include<memory>
#include<algorithm>
#define cin fin
using namespace std;
ifstream fin("hidden.in");
ofstream fout("hidden.out");
char s[200002];
char s1[200002];
int next[200002];
int maxn,n,m;
char ch;
int st,en,st2;
int main()
{
     int i,j,k;
 char a,b,c;
 cin>>n;
 cin.getline(s,100,'\n');
 while(cin.getline(s1,100,'\n'))
   strcat(s,s1);
     strcpy(s1,s);
     strcat(s,s1);
 maxn=0;
 ch=s[0];
 st=1;
 s[n]=s[0];
 int stat;
 while(st<n)
 {
      stat=0;
   for(i=0;i<n;i++){
    if(s[maxn+i]<s[st+i])
    {
        stat=-1;
        break;
             }
             else if(s[maxn+i]>s[st+i])
             {
                 stat=1;
                 break;
             }
   }
         if(i<n && stat>0) {
     maxn=st;
     ch=s[st];
    }
         else if(i<n && stat<0)
         {
             st+=i+1;
             continue;
         }
         else if(i==n)
         {
             stat=2;
             break;
         }
    st++;
 }
 if(stat==2) fout<<'0'<<endl;
 else fout<<maxn<<endl;
 return 0;
}