[洛谷]UVA10298 Power Strings

原题链接:https://www.luogu.com.cn/problem/UVA10298

[原题]

题目描述

PDF

输入格式

输出格式

题意翻译

题意简述：

求一个字符串由多少个重复的子串连接而成。

例如 ababab 由三个 ab 连接而成，abcd 由 abcd 由一个 abcd 连接而成。

输入格式

本题多组数据。

每一组数据仅有一行，这一行仅有一个字符串 ss。

输入的结束标志为一个 .。

输出格式

对于每一组数据，输出这组字符串由多少个重复的子串连接而成。

说明/提示

1\le |s|\le 10^61≤∣s∣≤106。

输入输出样例

输入 #1复制

abcd
aaaa
ababab
.

输出 #1复制

1
4
3

[题解]

首先我们一下一些可以通过重复字串构成的字符串的特点.

abcdabcdabcd aaaaaaaaa ababababab

然后相对应写出这些字符串里面的next数组(就是KMP算法中的next数组), 观察一下有什么特点.

000012345678 012345678 0012345678

我们会发现这种字符串其实除了前面有几个0以外后面是每次加1的, 前面的几个0就是我们需要寻找的重复字串.

为什么呢?

我们这样想.如果一个字符串是通过重复字符串的话, 字符串的next[n] ~  n 和 0 ~ next[N] 字符串 一定相同, 并且, 

n - next[n]就是最小的重复字串.