poj - 1509 - Glass Beads（最小表示法）

本文主要是介绍poj - 1509 - Glass Beads（最小表示法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：求一个字符串的最小表示的起始位置（字符串长度最大为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;
}

这篇关于poj - 1509 - Glass Beads（最小表示法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---