Power Strings
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 48867 Accepted: 20366

Description

Given two strings a and b we define a*b to be their concatenation. For example, if a = “abc” and b = “def” then a*b = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).

Input

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a^n for some string a.

Sample Input

Sample Output

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.
据说后缀数组倍增+rmq都超时了,我写完之后发现也超时了,不过证明后缀数组写的还算对,kmp留待填坑
首先构造sa,height等数组  height表示排名第i和排名i-1数组lcp是多少
增设rm数组  rm[排名]=与整个字符串的lcp
判断时,如果i不能被n整除那么也就不可能成为循环节 如果suffix[i+1]可以和整个字符串匹配,且匹配长度正好等于suffix[i+1]那么说明 循环节是n/i;

在做kmp之前首先还要复习一下kmp的定义包括求法等

kmp:给定两个字符串如T,S求 S在T 中能否匹配能的话返回匹配的位置

我们首先用一个图来描述kmp算法的思想。在字符串S中寻找T,当匹配到位置i时两个字符串不相等,这时我们需要将字符串T向前移动。常规方法是每次向前移动一位,但是它没有考虑前i-1位已经比较过这个事实,所以效率不高。事实上,如果我们提前计算某些信息,就有可能一次前移多位。假设我们根据已经获得的信息知道可以前移k位,我们分析移位前后的T有什么特点。我们可以得到如下的结论:

  • A段字符串是T的一个前缀。
  • B段字符串是T的一个后缀。
  • A段字符串和B段字符串相等。

所以前移k位之后,可以继续比较位置i的前提是T的前i-1个位置满足:长度为i-k-1的前缀A和后缀B相同。只有这样,我们才可以前移k位后从新的位置继续比较。

图片中 O代表S,f代表T

所以kmp算法的核心即是计算字符串f每一个位置之前的字符串的前缀和后缀公共部分的最大长度(不包括字符串本身,否则最大长度始终是字符串本身)。获得f每一个位置的最大公共长度之后,就可以利用该最大公共长度快速和字符串O比较。当每次比较到两个字符串的字符不同时,我们就可以根据最大公共长度将字符串f向前移动(已匹配长度-最大公共长度)位,接着继续比较下一个位置。事实上,字符串f的前移只是概念上的前移,只要我们在比较的时候从最大公共长度之后比较f和O即可达到字符串f前移的目的。

next数组计算

这个最大公共长度在算法导论里面被记为next数组

在这里要注意一点,next数组表示的是长度,下标从1开始;但是在遍历原字符串时,下标还是从0开始。

在求得next数组后例如
ababab  next[6] = 4; 即

ababab
ababab
1~4位  与2~6位是相同的

那么前两位
就等于3、4位
3、4位就等于5、6位
……
所以 如果 能整除  也就循环到最后了

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论