字符串的最小表示法

未分类

USACO 5.5.2

int get_min(char *s)
{
    int i = 0, j = 1;
    int len = strlen(s);
    while (i < len && j < len)
    {
        // printf("i=%4d,j=%4d\n",i,j);
        if (s[i] < s[j % len])
            j++;
        else if (s[i] > s[j % len])
        {
            i = j;
            j = i + 1;
        }
        else
        {
            int k;
            for (k = 1; k < len && s[(i + k) % len] ==  s[(j + k) % len]; k++);
            if (k == len) //出现循环节
                return i;
            if (s[(i + k) % len] > s[(j + k) % len])
            {
                i = j;
                j = i + 1;
            }
            else
            {
                j = j + k + 1; // i .. j - 1 和 j 开头的都不是最小表示,
            }
        }
    }
    return i;
}

POJ 1509

int min_p(const char *s)
{
    int len = strlen(s);
    int i = 0, j = 1, k;
    while (i < len && j < len)
    {
        for (k = 0; k < len && s[(i + k) % len] == s[(j + k) % len]; k++);
        if (k == len)
            return i;
        if (s[(i + k) % len] > s[(j + k) % len])
            swap(i,j);
        j = max(i+1,j + k + 1);
    }
    return i;
}

在此输入正文