题意:求一个字符串的最小表示的起始位置(字符串长度最大为10000)。
题目链接:http://poj.org/problem?id=1509
——>>很久以前就听过师兄说最小表示,今天看周源的《浅析“最小表示法”思想在字符串循环同构问题中的应用》,找了这题,与论文里描述的题目一样。。
我觉得这个思想挺不错:一直维护着字典序较小的指针。。让另一个指针不断地缩小字典序。。直至成功或者失败结束。。
#include <cstdio> #include <cstring> using namespace std; const int maxn = 10000 + 10; char s[maxn]; int min_representation(char *s) { int len = strlen(s); int i = 0, j = 1, k; char c1, c2; while(1) { for(k = 0; k < len; k++) { c1 = s[(i+k)%len]; c2 = s[(j+k)%len]; if(c1 != c2) break; } if(k == len) break; if(c1 > c2) { i += k + 1; if(i == j) i++; } else { j += k + 1; if(j == i) j++; } } return i < j ? i : j; } int main() { int n; while(scanf("%d", &n) == 1) { for(int i = 0; i < n; i++) { scanf("%s", s); printf("%d\n", min_representation(s)+1); } } return 0; }