UVA1584 UVALive3225 Circular Sequence

Regionals 2004 >> Asia - Seoul

问题链接：UVA1584 UVALive3225 Circular Sequence。基础训练级的题，用C语言编写。

这个问题是寻找循环串中的最小者。

不移动字符串是关键，不然就会浪费时间。

程序中，封装了两个功能函数cirstrcmp()和cirstrprintf()，使得主程序的逻辑大为简化。这两个函数是通用性的函数，完全封装，与全局变量没有关系。

AC通过的C语言程序如下：

/* UVA1584 UVALive3225 Circular Sequence */

#include <stdio.h>
#include <string.h>

#define MAXN 100

/* 循环串比较，a[s]和a[t]开始的两个串进行比较，s>t,s=t,s<t返回值分别为负,0,正 */
int cirstrcmp(char a[], int s, int t, int length)
{
    int count, i, j;

    count = length;
    for(i = s, j = t; count-- > 0; i = ++s % length, j = ++t % length) {
        if(a[i] == a[j])
            continue;
        return a[i] - a[j];
    }

    return 0;
}

void cirstrprintf(char a[], int start, int length)
{
    int count=0, i;

    for(i = start; count++ < length; i = (i + 1) % length)
        putchar(a[i]);
    putchar('
');
}

int main(void)
{
    int t, min, len, i;
    char s[MAXN+1];

    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);

        len = strlen(s);

        min = 0;
        for(i=1; i<len; i++)
            if(cirstrcmp(s, i, min, len) < 0)
                min = i;

        cirstrprintf(s, min, len);
    }

    return 0;
}