HDU 3374 String Problem(最小表現+KMP求周期)

/*
  ：     ，             ，      

  ：      + KMP
                    
    KMP           
*/


#include <iostream>
using namespace std;
const int nMax = 1000010;
char S[nMax];
int next[nMax];

int solve1(int len)//     
{
	int i, j, k;
	for(i = 0, j = 1, k = 0;i < len && j < len && k < len;)
	{
		int t = S[(i + k) % len] - S[(j + k) % len];
		if(t == 0)
			k ++;
		else
		{
			if(t > 0) i += k + 1;
			else if(t < 0) j += k + 1;
			k = 0;
			if(i == j)
				j ++;
		}
	}
	return min(i, j);
}

int solve2(int len)//     
{
	int i, j, k;
	for(i = 0, j = 1, k = 0;i < len && j < len && k < len;)
	{
		int t = S[(i + k) % len] - S[(j + k) % len];
		if(t == 0)
			k ++;
		else
		{
			if(t > 0) j += k + 1;//            
			else if(t < 0) i += k + 1;
			k = 0;
			if(i == j)
				j ++;
		}
	}
	return min(i, j);
}

void getNext(int len)//KMP  next[]
{
	next[0] = -1;
	int i = 0;
	int j = -1;
	while(i < len)
	{
		if(j == -1 || S[i] == S[j])
		{
			i ++;
			j ++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

int main()
{
	//freopen("e://data.txt", "r", stdin);
	while(scanf("%s", S) != EOF)
	{
		int len = strlen(S);
		int pos1, pos2;
		pos1 = solve1(len);
		pos2 = solve2(len);
		getNext(len);
		int c = len - next[len - 1] - 1;//c       
		if(len % c == 0)
			c = len / c;
		else//        ，    1
			c = 1;
		printf("%d %d %d %d
", pos1 + 1, c, pos2 + 1, c);
	}
	return 0;
}