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（最小表示法）,布布扣,bubuko.com

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

原文：http://blog.csdn.net/scnu_jiechao/article/details/22999195