Visits: 109

计蒜客 – 旋转数字

蒜头君发现了一个很好玩的事情，他对一个数作旋转操作，把该数的最后的数字移动到最前面。比如，数 123123 可以得到 312, 231, 123312,231,123，这样就可以得到很多个数。

现在，蒜头君的问题是这些数中，有多少个不同的数小于原数，多少个等于原数，多少个大于原数。

旋转中可能会出现前导零，两数比较的时候可以忽略前导零的影响。

输入格式

输入一个整数 $N(0 < N\leq 10^{100000})$。

341

输出格式

答案在一行中输出三个整数，分别是小于 N，等于 N，大于 N 的个数，中间以空格隔开。

1 1 1

这道题是一道利用拓展 KMP 算法的好题目。

我们一点一点来剖析这道题。

第一个问题，怎么枚举出所有旋转得到的数字？

把数字收尾相接，然后从第 0 个位置到第 length 个位置，每次往后取 length 个长度的字符，就可以遍历出所有可能的 length 个数字。

char num[MAX_LEN];
scanf("%s", num);
int len = strlen(num);
char* numnum = duplicate(num);
for (int i = 0; i < len; i++) {
    for (int j = i; j < i + len; j++) {
        printf("%c", numnum[j]);
    }
    printf("\n");
}

char* concat(const char* s1, const char* s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    char* s3 = (char*)malloc(sizeof(char) * (len1 + len2 + 1));
    strncpy(s3, s1, len1);
    strncpy(s3 + len1, s2, len2);
    s3[len1 + len2] = '\0';
    return s3;
}

char* duplicate(const char* s) {
    return concat(s, s);
}

第二个问题，怎么比较大小？

由于数字非常大，我们不可能每次都转成整型以后去比较大小，而利用字符串相等来比较数字之间的大小，是一种常用的做法。

首先让我们考虑怎么比较两个数字相等，显然，那就是这两个字符串相等，即 strcmp(s1, s2) == 0，对应到 KMP 算法中，那就是 next[s[i]] = length。

parseInt(s1) === parseInt(s2)
// 等价于
s1 === s2

当然，这里忽略了前导零，因为 s1 = '001' 和 s2 = '01'，显然 parseInt(s1) === parseInt(s2) 是成立的，但是 s1 === s2 是不成立的。

可是，由于题目要求的是不同的数字，所以我们不需要考虑重复数字，那么，在这种情况下，与原数相等的数字就只有 1 个了。

所以我们只需要比较大于，或者小于原数的数字。

给定两个字符串 s1 和 s2，如果已知他们开始的 x 个字符都相等，如何判断它们的大小？只需要比较第 x + 1 个位置上的字符的大小就可以了。

而前 x 个字符都相等，这一点 next[] 数组已经帮我们做好了，所以我们只需要比较 numnum[i + next[i]] 和 numnum[1 + next[i]] 的大小。

int greater = 0;
int equal = 0;
int less = 0;
for (int i = 1; i <= len; i++) {
    if (next[i] == len * 2) {
        equal++;
    } else if (numnum[i + next[i]] < numnum[1 + next[i]]) {
        less++;
    } else {
        greater++;
    }
}
printf("%d %d %d", less, equal, greater);

下面还剩两个问题，第一个，如何去除循环，第二个，如何解决前导零。

在解决这两个问题之前，我们先来看一组样例。

对于 123123 这个数，我们期望得到的数字是 123123、231231、312312 这 3 个，而不是将 123123 变成 123123123123 之后枚举出来的 6 个。

所以，能不能通过将数字只复制最小的循环节来完成？

答案是显然的。

求循环节的过程之前已经介绍过了，就是利用 n - next[n] 即可，那么我们只需复制这样一小节拼在最后就可以了。

// 求出字符串 t 的循环节长度
int getLoop(const char *t, int length) {
    int *next = (int *) malloc(sizeof(int) * (length + 1));
    next[1] = 0;
    for (int i = 2; i <= length; i++) {
        int j = next[i - 1];
        while (t[j + 1] != t[i] && j > 0) {
            j = next[j];
        }
        if (t[j + 1] == t[i]) {
            next[i] = j + 1;
        } else {
            next[i] = 0;
        }
    }
    return length - next[length];
}

char *duplicate(const char *s) {
    int len = strlen(s + 1);
    int loop = getLoop(s, len);
    char *ss = (char *) malloc(sizeof(char) * (len + loop + 2));
    strncpy(ss + 1, s + 1, len);
    strncpy(ss + 1 + len, s + 1, loop);
    ss[1 + len + loop] = '\0';
    return ss;
}

那么与之对应的，for (int i = 1; i <= len; i++) 中的 len，就应该换成循环节的长度 getLoop(num + 1, strlen(num + 1))。

这样一来，重复数字的问题也就自然而然地被解决了。前导零也不需要特别处理了。

但是这么做的话，123123 可以被正常处理，123123123 也可以得到正确的结果，因为对于他们来说，循环节都是 123，只需要拼接一段循环节到最后就可以了。

然而，12312312312 求出的循环节 123 可不能被简单地拼接到最后，因为对于这个数字来说，12312312312 才是需要被拼接的。

所以我们需要判断一下，最后一个是不是真的完整的循环节。

int loop = length - next[length];
if (next[length] % loop != 0) {
    return length;
} else {
    return loop;
}

由此，可以得到完整代码：

#include <bits/stdc++.h>

//#define DEBUG_USE_ONLY
#define MAX_LEN 100007

void print(const char *t, const int *next, int n) {
    for (int i = 1; i <= n; i++) {
        printf("%c%c", t[i], i == n ? '\n' : '\t');
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", next[i], i == n ? '\n' : '\t');
    }
}

// 求出字符串 t 的循环节长度
int getLoop(const char *t, int length) {
    int *next = (int *) malloc(sizeof(int) * (length + 1));
    next[1] = 0;
    for (int i = 2; i <= length; i++) {
        int j = next[i - 1];
        while (t[j + 1] != t[i] && j > 0) {
            j = next[j];
        }
        if (t[j + 1] == t[i]) {
            next[i] = j + 1;
        } else {
            next[i] = 0;
        }
    }
    int loop = length - next[length];
#ifdef DEBUG_USE_ONLY
    print(t, next, length);
    printf("[%d]\n", loop);
#endif
    if (next[length] % loop != 0) {
        return length;
    } else {
        return loop;
    }
}

char *duplicate(const char *s, int len, int loop) {
    char *ss = (char *) malloc(sizeof(char) * (len + loop + 2));
    strncpy(ss + 1, s + 1, len);
    strncpy(ss + 1 + len, s + 1, loop);
    ss[1 + len + loop] = '\0';
    return ss;
}


int *getNext(const char *t, int n) {
    int *next = (int *) malloc(sizeof(int) * (n + 1));
    next[1] = n;
    int p = 1;
    while (p < n && t[p] == t[p + 1]) p++;
    next[2] = p - 1;
    int k = 2, l;
    for (int i = 3; i <= n; i++) {
        p = k + next[k] - 1;
        l = next[i - k + 1];
        if (i + l <= p) next[i] = l;
        else {
            int j = p - i + 1;
            if (j < 0) j = 0;
            while (i + j <= n && t[i + j] == t[j + 1]) j++;
            next[i] = j;
            k = i;
        }
    }
    return next;
}

int main() {
    char num[MAX_LEN];
    scanf("%s", num + 1);
    int len1 = strlen(num + 1);
    int loop = getLoop(num, len1);
    char *numnum = duplicate(num, len1, loop);
    int len2 = strlen(numnum + 1);
    int *next = getNext(numnum, len2);
#ifdef DEBUG_USE_ONLY
    print(numnum, next, len2);
#endif
    int greater = 0;
    int equal = 0;
    int less = 0;
    for (int i = 1; i <= loop; i++) {
#ifdef DEBUG_USE_ONLY
        for (int j = i; j < i + len1; j++) {
            printf("%c", numnum[j]);
        }
        printf(", next = %d, %c - %c\n", next[i], numnum[i + next[i]], numnum[1 + next[i]]);
#endif
        if (next[i] == len2) {
            equal++;
        } else if (numnum[i + next[i]] < numnum[1 + next[i]]) {
            less++;
        } else {
            greater++;
        }
    }
    printf("%d %d %d", less, equal, greater);
    return 0;
}