循环节

循环节

问题描述

小粽今天在玩一个字符串。

最初，小粽手上有很多很多个（你可以认为是无限多个）一模一样的字符串 aa，小粽选出若干个 aa 顺次拼接为一个新的字符串 bb。

由于小粽犯了粗心，她把最初的 aa 搞丢了，并且 bb 的末尾也丢失了一些字符，只剩下了一个 bb 的前缀 cc。

小粽很伤心，为了安慰她，请帮她计算可能的 aa 的最短长度是多少。

输入格式

第一行一个正整数 nn，表示 cc 的长度。第二行一行一个字符串，描述字符串 cc。

输格式

输出一行一个整数，表示 aa 的可能的最短长度。

输入样例 1

输样例 1

样例 1 解释

最短的 aa 为 cab。

样例 2

点此下载。

数据规模及约定

对于 20%20% 的数据有 n≤100n≤100； 对于 50%50% 的数据有 n≤6000n≤6000；

对于 70%70% 的数据有 n≤2×105n≤2×105；

对于 100%100% 的数据有 1≤n≤1061≤n≤106，并且 cc 中只有小写字母。

提示

[ 猜不到结论？手动画几个找找规律呗]

代码

#include <cstdio> #include <cstring>

#pragma warning(disable:4996)； #define maxl 1000000

/* =========== 代码实现开始 =========== */

void getNext(char *s, int len, int next[])

{

int i = 0, j = -1;

next[0] = -1;

while (i < len)

{

if (-1 == j || s[i] == s[j])

next[++i] = ++j;

else

j = next[j];

}

}

int next[maxl + 10];

// s, len: 输入字符串（题目中的c）及长度

// 返回值：题目中 a 串的最短长度int solve(char *s, int len)

{

getNext(s, len, next);

if (next[len] == 0)

return len;

else

return len - next[len];

}

/* =========== 代码实现结束 =========== */

char s[maxl + 10];

int main()

{

int len;

scanf("%d%s", &len, s);

printf("%d\n", solve(s, len));

return 0;

}