题意

如果一个字符串由一个子串不断拼接自己形成，如abcabcabc由abc拼接形成，如果随便从这个大字符串截取一段长度大于子串的长度的字符串，问能不能求出这个周期子串的长度

[BOI2009] Radio Transmission 无线传输

题目描述

给你一个字符串 $s_1$，它是由某个字符串 $s_2$ 不断自我连接形成的（保证至少重复 $2$ 次）。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行一个整数 $L$，表示给出字符串的长度。

第二行给出字符串 $s_1$ 的一个子串，全由小写字母组成。

输出格式

仅一行，表示 $s_2$ 的最短长度。

样例 #1

样例输入 #1

8
cabcabca

样例输出 #1

3

提示

样例输入输出 1 解释

对于样例，我们可以利用 $\texttt{abc}$ 不断自我连接得到 $\texttt{abcabcabcabc}$，读入的 $\texttt{cabcabca}$，是它的子串。

规模与约定

对于全部的测试点，保证 $1 < L \le 10^6$。

对于答案来说就是N-next[N]

对于一个由于周期子串组成的字符串来说，周期不一定要是先前的周期子串，比如周期子串abc
大串abcabcabcabc，截取成cabcabca，截取的字符串的周期可以是cab，虽然不同，但是长度相同
另外，周期子串组成的字符串的next数组的第一个周期是0，后面的周期是从1开始递增的
比如abcabcabc
next数组就是000123456

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

void solve()
{
    cin>>n>> p + 1;
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
    cout << n - ne[n] << '\n';
}