hdu3374+字符串+kmp+最小表示

给定一个字符串，问你最小表示需要移动多少位，且有多少种最小表示？

two point 维护 如果相等就共同k++,不相等就移位+=k+1;k变为0；为什么可以？没想清
后面的话就是循环节了！这个好求

using namespace std;
typedef long long LL;
const int Maxn=1e6+7;
int Next[Maxn];
char s[Maxn];
int (const char P[],int Next[])
{
    int q,k;
    int m = strlen(P);
    Next[0] = 0;
    for (q=1,k=0; q<m; ++q)
    {
        while(k>0 && P[q]!=P[k])  k=Next[k-1];
        if (P[q] == P[k]) k++;
        Next[q] = k;
    }
    return m;
}
int min_max_exp(char *s,int len,int flag){
	int i=0,j=1,k=0;
	while(i<len && j<len && k<len){
		int t=s[(j+k)%len]-s[(i+k)%len];
		if(t==0) k++;
		else {
			if(flag){
				if(t>0) j+=k+1;
				else i+=k+1;
			}
			else{
				if(t>0) i+=k+1;
				else j+=k+1;
			}
			if(i==j) j++;
			k=0;
		}
	}
	return min(i,j);
}
int main()
{
	while(~scanf("%s",s)){
		int len=getnext(s,Next);
		int Min=min_max_exp(s,len,1);
		int Max=min_max_exp(s,len,0);
		int ans=(len%(len-Next[len-1]))?1:len/(len-Next[len-1]);
		printf("%d %d %d %dn",Min+1,ans,Max+1,ans);
	}
	return 0;
}