【题解】Revolving Digits 扩展 KMP HDU – 4333

题目链接

扩展 KMP 原来这么好写

强烈推荐 boshi 写的教程：戳我戳我！

这题的话就是枚举旋转次数

旋转完的字符串就是一段后缀+一段前缀

那么判断大小关系就是要找到一个不相同的位置

所以就先找到那段后缀与原串的最长公共前缀（LCP）

如果 LCP 长度是小于这段后缀的长度的，说明不同的字符在这段后缀里，判断就行了

如果 LCP 长度等于这段后缀的长度，说明不同的字符在接在后缀后面的那个前缀里（或者没有不同的字符），那就判断那个前缀与原串减去 LCP 剩下的那个后缀的最长公共前缀

如果这个最长公共前缀依然等于剩下的前缀，那说明两者完全相同，也就说明出现了循环节

由于相同的数字只统计一次，因此遇到循环节直接退出就行了

扩展 KMP 在维基百科上称为 “Z algorithm”，国内所说的 next 数组被称为 z 函数，以下代码用了这样的命名

_(:зゝ∠)_

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>

#define NS (100005)

using namespace std;

int testcase, n, z[NS], al, ar;

char s[NS];

void getz()
{
    memset(z + 1, 0, sizeof(int) * n), z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; i += 1)
        if (i > r)
        {
            while (s[i + z[i]] == s[1 + z[i]]) z[i]++;
            l = i, r = i + z[i] - 1;
        }
        else
        {
            z[i] = min(r - i + 1, z[i - l + 1]);
            while (s[i + z[i]] == s[1 + z[i]]) z[i]++;
            if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
        }
}

int main(int argc, char const* argv[])
{
    scanf("%d", &testcase);
    for (int C = 1; C <= testcase; C += 1)
    {
        scanf("%s", s + 1), n = strlen(s + 1), getz(), al = ar = 0;
        for (int i = 2; i <= n; i += 1)
            if (i + z[i] > n)
            {
                int j = 1 + z[i];
                if (j + z[j] > n) break;
                if (s[j + z[j]] > s[1 + z[j]]) al++;
                else ar++;
            }
            else if (s[i + z[i]] < s[1 + z[i]]) al++;
            else ar++;
        printf("Case %d: %d 1 %d\n", C, al, ar);
    }
    return 0;
}