题目描述

给定若干个的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 最多由 $3$ 个 ab 连接而成。

输入格式

输入若干行，每行有一个字符串，字符串仅含英文字母。特别的，字符串可能为.，即一个半角句号，此时输入结束。

输出格式

输出每个字符串最多是由多少个相同的子字符串重复连接而成。

样例

样例输入

abcd
aaaa
ababab
.

样例输出

1
4
3

数据范围与提示

对于 $100\%$ 的数据，满足 $1≤字符串长度≤10^6$

代码：（80 pts）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s[1000001];
int nxt[1000001];
int main() {
    while (1) {
    	scanf("%s", s + 1);
		if (s[1] == '.') return 0;
		int i = 2, j = 0; nxt[1] = 0;
		while (i <= strlen(s + 1)) {
			if (j == 0 || s[i] == s[j + 1]) {
				i++; j++;
				nxt[i] = j;
			} else {
				j = nxt[j];
			}
		}
		if (strlen(s + 1) % (strlen(s + 1) - nxt[strlen(s + 1)]) == 0) {
			cout << strlen(s + 1) / (strlen(s + 1) - nxt[strlen(s + 1)]) << "\n";
		} else {
			cout << 1 << "\n";
		}
	}
    return 0;
}

调对必关