【bzoj1335】Radio Transmission

给你一个字符串，它是由某个字符串不断自我连接形成的。
但是这个字符串是不确定的，现在只想知道它的最短长度是多少.

因为这个字符串是不断自匹配形成的我们可以很容易的想到，除了第一个字符串外，从第二个字符串开始，根据这样一个过程：
cabcabca
i=1 0 j=1
i=2 0
i=3 0
i=4 1
i=5 -> j=4 -> 2
i=6 3
i=7 4
i=8 -> j=7 -> 5
也就是说，除了第一个字符串外
剩下的都可以通过next数组的辅助平移是匹配进行下去
这样就是说在next数组中，除了第一个字符串外，剩下的存储在next数组中的数是从1开始逐个递增的，这样就是说，最后我们用组合字符串长度n减去next[n]就能得到最小循环元的长度

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000086;
int n;
char a[maxn];
int Next[maxn];

inline int read() {
    int x = 0, y = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') y = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x * y;
}

int main() {
    n = read();
    cin >> a + 1;
    Next[1] = 0;
    for(int i = 2, j = 0; i <= n; ++i) {
        while(j > 0 && a[i] != a[j + 1]) j = Next[j];
        if(a[i] == a[j + 1]) j++;
        Next[i] = j;
    }
    cout << n - Next[n] << '
';
    return 0;
}