有时候程序员有很奇怪的方法来隐藏他们的口令。Binny会选择一个字符串S（由N个小写字母组成，5<=N<=5,000,000），然后他把S顺时针绕成一个圈，每次取一个做开头字母并顺时针依次取字母而组成一个字符串。这样将得到一些字符串，他把它们排序后取出第一个字符串。把这个字符串的第一个字母在原字符串中的位置-1做为口令。
如字符串alabala，按操作的到7个字符串，排序后得：
aalabal
abalaal
alaalab
alabala
balaala
laalaba
labalaa
第一个字符串为aalabal，这个a在原字符串位置为7，7-1=6，则6为口令。

输入格式：

第一行：一个数：N
第二行开始：字符串：S（每72个字符一个换行符）

输出格式：

一行，为得到的口令

输入样例#1：

7
anabana

输出样例#1：

6

题目满足：

30%的数据n<=10000
70%的数据n<=100000
100%的数据n<=5000000

题解：

题目的意思其实就是让你才能从两个拼起来的相同的串中，找出长度为n的字典序最小的连续子串。
很容易想到暴力是把所有的串都存下来，并记录下其位置，然后排序，找到最小的串输出位置即可。
但是数据范围很大，我们就可以通过比较每两个来得到最小的。
首先我们定义两个指针，分别代表以其所开头的串的位置。
然后从这两个位置往后比较，如果这一位相同，继续比较下一位，如果比较到某一位上，第一个串这一位大于第二个串，则说明第二个串比第一个串更优，所以我们将第一个串的头放在第二个串的位置，让第二个串的头向下移一位，如果第一个串这一位小于第二个串，那么就说明第二个串不如第一个串优，则我们将第二个串的头放到匹配失败的这一位的后面，因为前面都一样字母（可以自己写一下实验），所以往后移一位还是不如前一个串优。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s1[10000050], s2[5000050];
int main()
{
    int n;
    cin >> n;
    int tot = 1;
    for (int i = 1; i <= n; i++)
        cin >> s2[i];
    for (int i = 1; i <= n; i++)
    {
        s1[i] = s2[i];
        s1[i+n] = s2[i];
    }
    int ans = 1;
    int s = 1, t = 2;
    for (int i = 0; i <= n, s <= n, t <= n+1;)
    {
        while (s1[s+i] == s1[t+i] && i <= n-1 && s <= n && t <= n+1)
            i++;
        if (i == n)
            break;
        if (s1[s+i] < s1[t+i])
            t = t+i+1, i = 0, ans = s;
        else if (s1[s+i] > s1[t+i])
        {
            s = t;
            t++;
            i = 0;
            ans = s;
        }
    }
    cout << ans-1;
    return 0;
}
/*
7
alabala
7
asdasfs
*/