1223.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1223 on 2005-12-31 at 15:37:51 */ 
#include <cstdio>
#include <cstring>


const int MAX = 204800;

int main()
{
	int l, t, T, i;
	char word[MAX];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %s", &l, word);
		strcpy(word+l+1, word+1);
		word[l] = word[0];
		int bp = 0, cp = 0;
		while(word[cp] == word[bp] && cp < l) cp++;
		while(cp < l) {
			for(i = 0; i < l; i++) {
				if(word[bp+i] != word[cp+i]) break;
			}
			if(i == l || word[bp+i] < word[cp+i]) {
				cp += i + 1;
			} else {
				bp = cp;
				while(word[cp] == word[bp] && cp < l) cp++;
			}
		}
		printf("%d\n", bp);
	}
	
	return 0;
}