HDU 4333 – Revolving Digits [扩展KMP]

Link

传送门

Problem

One day Silence is interested in revolving the digits of a positive integer. In the revolving operation, he can put several last digits to the front of the integer. Of course, he can put all the digits to the front, so he will get the integer itself. For example, he can change 123 into 312, 231 and 123. Now he wanted to know how many different integers he can get that is less than the original integer, how many different integers he can get that is equal to the original integer and how many different integers he can get that is greater than the original integer. We will ensure that the original integer is positive and it has no leading zeros, but if we get an integer with some leading zeros by revolving the digits, we will regard the new integer as it has no leading zeros. For example, if the original integer is 104, we can get 410, 41 and 104.

Mean

给你一个原始数字,你可以将后面的一个数字移动到前面,这样就生成了好多数字。如341可以生成341、134、413,问你这些数字小于等于大于原始数字的数各有多少个。

Analysis

可以将341组合成341341,然后求出341341中每个后缀与341的最长公共前缀,找出公共前缀了只需要O(1)时间判断公共前缀后面一个数字的大小即可。求字符串每个后缀与另一个字符串的最长公共前缀可以用KMP。这里直接套模板了。

注意有循环的情况,如给定123123,那么可以生成3种情况而不是6中情况。可以用普通的kmp求出原串的最短循环串。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 204800;
int fail[maxn], extend[maxn];
char s1[maxn], s2[maxn];

/**
 * fail[i]: x[i...m-1]与x[0...m-1]的最长公共前缀
 * extend[i]: y[i...n-1]与x[0...m-1]的最长公共前缀
 */
void pre_EKMP(char x[], int m, int fail[]) {
    fail[0] = m;
    int j = 0, k = 1;
    while (j + 1 < m && x[j] == x[j + 1]) ++j;
    fail[1] = j;
    for (int i = 2; i < m; i++) {
        int p = fail[k] + k - 1;
        int L = fail[i-k];
        if (i + L < p + 1) fail[i] = L;
        else {
            j = max(0, p - i + 1);
            while (i + j < m && x[i+j] == x[j])j++;
            fail[i] = j;
            k = i;
        }
    }
}
void EKMP(char x[], int m, char y[], int n, int fail[], int extend[]) {
    pre_EKMP(x, m, fail);
    int j = 0, k = 0;
    while (j < n && j < m && x[j] == y[j]) ++j;
    extend[0] = j;
    for (int i = 1; i < n; i++) {
        int p = extend[k] + k - 1;
        int L = fail[i-k];
        if (i + L < p + 1) extend[i] = L;
        else {
            j = max(0, p - i + 1);
            while (i + j < n && j < m && y[i+j] == x[j]) ++j;
            extend[i] = j;
            k = i;
        }
    }
}

void getFail(const char *P, int *f, int len) {
    f[0] = f[1] = 0;
    for(int i = 1; i < len; ++i) {
        int j = f[i];
        while(j && P[i] != P[j]) j = f[j];
        f[i+1] = P[i]==P[j] ? j+1 : 0;
    }
}


int main() {
    int T, kase = 0; scanf("%d", &T);
    while (T--) {
        scanf("%s", s1);
        int len1 = strlen(s1);
        for(int i = 0; i < len1; ++i)
            s2[i] = s2[i+len1] = s1[i];
        int len2 = 2 * len1;
        s2[len2] = 0;
        EKMP(s1, len1, s2, len2, fail, extend);
        int cnt1 = 0, cnt2 = 0, cnt3 = 0;
        for(int i = 0; i < len1; ++i) {
            int cur = extend[i];
            if(cur >= len1) ++cnt2;
            else {
                if(s2[i+cur] < s1[cur])
                    ++cnt1;
                else ++cnt3;
            }
        }
        getFail(s1, fail, len1);
        int t = len1 - fail[len1];
        int tot = len1 % t ? 1 : len1 / t;
        printf("Case %d: %d %d %d\n", ++kase, cnt1/tot, cnt2/tot, cnt3/tot);
    }
    return 0;
}

欢迎留言