HDU3746 Cyclic Nacklace

KMP的一个第一个小应用，求循环节。
昨天开始学字符串，晚上的时候看了很多博客，但都讲的很乱，很复杂，直到看到了这篇 (传送门) 最后在纸上跟着模拟了一下，才算个人意义上的理解了。包括一个小优化。

这道题只有你理解了kmp的next的数组求法才会做。

题意：
一串珠子，要你再加最少的珠子满足，珠子循环大于等于2。比如abcabc，你只能在左右两边加。

思路：
kmp的next数组保存的是以当前位置的前一位置结尾的字符串中最长的相同前后缀长度。
因为字符串是循环的，比如abcabcab，那么 中间的abc 为前后缀所共有，所以 next[len] = 5，因此的，len – next[len] 就是最短循环的长度了。得到循环节的长度问题也就随之而解了。

刚看到这道题的时候我还以为是一开始就是个环，可以在任意位置插入，那样的话就稍显麻烦了，虽然原理相同，我现在的水平只能想到循环暴力求。但明显复杂度不满足要求……

AC Code

#include <cstring>
#include <iostream>
using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int nxt[maxn];
char src[maxn], des[maxn];
int slen, tlen;

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < tlen)
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
}

int main()
{
    int T_T;
    scanf("%d", &T_T);
    while (T_T--) {
        scanf("%s", des);
        tlen = strlen(des);
        getNext();
        int len = tlen - nxt[tlen];
        if (tlen != len && tlen % len == 0)
            puts("0");
        else
            printf("%d\n", len - nxt[tlen] % len);
    }
    return 0;
}