/*
tju 3275(Windy's S), zju2006(Glass Beads),
*/
//2302935 2010-04-06 19:52:55 Accepted 3374 468MS 11096K 1800 B C++ Xredman 

#include <iostream>
#include <string>
using namespace std;

const int N = 1000003;
int next[N];

/*
用最小表示法求字符串S的最小字典序
*/
int MaxRepresstation(string S)
{
	int i = 0, j = 1, k = 0;
	int len = S.length();
	S += S;
	while(i < len && j < len)
	{
		k = 0;
		while(k < len && S[i + k] == S[j + k])
			k++;
		if(k >= len)
			break;
		if(S[i + k] < S[j + k])
			i = max(i + k + 1, j + 1);
		else
			j = max(i + 1, j + k + 1);
	}
	return min(i ,j);
}

int MinRepresstation(string S)
{
	int i = 0, j = 1, k = 0;
	int len = S.length();
	S += S;
	while(i < len && j < len)
	{
		k = 0;
		while(k < len && S[i + k] == S[j + k])
			k++;
		if(k >= len)
			break;
		if(S[i + k] > S[j + k])
			i = max(i + k + 1, j + 1);
		else
			j = max(i + 1, j + k + 1);
	}
	return min(i ,j);
}

void getNext(string T)
{
	int j, k;
	int len = T.length();
	j = 0; k = -1; next[0] = -1;
	while(j < len)
		if(k == -1 || T[j] == T[k])
			next[++j] = ++k;
		else
			k = next[k];

}

int KMP_Count(string S, string T)
{
	int ans = 0;
	int slen = S.length(), tlen = T.length();
	int i, j = 0;
	if(slen == 1 && tlen == 1)
	{
		if(S[0] == T[0])
			return 1;
		else
			return 0;
	}
	getNext(T);
	for(i = 0; i < slen; i++)
	{
		while(j > 0 && S[i] != T[j])
			j = next[j];
		if(S[i] == T[j])
			j++;
		if(j == tlen)
		{
			ans++;
			j = next[j];
		}
	}
	return ans;
}
int main()
{
	string S, T;
	int repc;
	int Minbeg, Maxbeg, k, len;
	while(cin>>S)
	{
		Minbeg = MinRepresstation(S);
		Maxbeg = MaxRepresstation(S);
		T = S;
		S += S;
		S[S.length() -1] = '*';
		repc = KMP_Count(S, T);
		cout<<Minbeg + 1<<" "<<repc<<" "<<Maxbeg + 1<<" "<<repc<<endl;
	}
	return 0;
}

• 相关文章
• 全局相关文章