最小表示法

咳咳，我又回来了，有大半个月没更新了，最近我在刷题的时候刷到一个很有意思的字符串的题。题目大概长成这样：

给定一个循环字符串S的一个周期

题目：求S的字典序最小的周期

(比如 abc,bca,cab都是同一个循环字符串，这个循环字符串的最小表示是abc)

Input

有多组数据

每组数据只有一行

是只由小写字母组成的字符串

每行字符个数不超过20万

总字符个数不超过100万

Output

输出S的字典序最小的一个周期

SampleInput

aabaaaaabb
bbbababa
bbacccca
baddd

SampleOutput

aaaaabbaab

abababbb

abbacccc

adddb

我当时拿到题目也没多想，直接暴力，毕竟是环嘛，从头到尾，暴力搜索一边就好了，然鹅....

TLE了QAQ，当时看了下数据量足足100W，也不知道怎么做，然后去网上搜了下大佬的博客，发现这也是一个算法叫作 最小表示法

它的复杂度好像是 O(n)，自然效率高得多，然后AC了，还是蛮有意思的算法，下面看看吧。

这个最小表示法，原理大概是这样：

把已经比较过相等的字符跳过，从最后一个相等的字符的下一个字符开始比较字典序。这里需要用到两个指针i,j,

Of Course,你也可以把这两个指针名字改一，然后令i=0，j=1 k=0(或者换一下i=1.j=0，然是必须保证从字符串的头开始)

然后依次判断第i+k个位置字符和第j+k个位置的字符的关系

1> 当第i+k个位置的字符等于第j+k(不是DJ！=_=)个位置的字符的时,k++；

2> 当第i+k个位置的字符小于第j+k个位置的字符时，j=j+k+1;(因为第i+k个位置之前的位置的字符和第j+k个位置之前的位置的字符都是相等的，第i+k个位置小于j+k，说明第i个位置的字符比j更优，保留i，j+=k+1)；

3> 当第i+k个位置的字符大于第j+k个位置的字符时，i=i+k+1;

(因为第i+k个位置之前的位置的字符和第j+k个位置之前的位置的字符都是相等的，第i+k个位置大于j+k，说明第j个位置的字符比i更优，保留j，i+=i+1)；4>当遍历完成时，取i，j之中最小的就是字典序最小的循环同构串。这里面还有几个注意的地方：1>用k递增的时候要对i+k对数组长度取模，防止溢出； 2>每次第i+k个元素！=第j+k个元素的时候将k置零； 3>当i==j时，变化的指针++，要让i，j指针不在同一个位置； 这大概就是这个算法的大体思路，下面我给出源代码：

#include
using namespace std;
int len;
char c[200005];
int main(void)
{
    while(~scanf("%s",c))
    {
        int cout=0,i=0,j=1,k=0;
        len=strlen(c);
        while(i