题目地址：POJ2406【Power Strings】
题目描述： Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “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).
输入描述： 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.
输出描述： For each s you should print the largest n such that s = a^n for some string a.
输入描述：
abcd aaaa ababab .输出样例：
1 4 3注释： This problem has huge input, use scanf instead of cin to avoid time limit exceed.
题意： 给出两个字符串a和b，定义ab是它们的串联。 例如：如果a=“abc”，b=“def”，则ab=“abcdef”。 如果把串联视为相乘，非负整数指数则定义为：a^0=" "（空串），而a^(n+1)=a* (a^n)。 输入 每个测试用例是在一行中给出一个可打印字符的字符串s。s的长 度将至少为1，并且不会超过1000000（一百万）个字符。在最后 一个测试用例后面，给出包含句点的一行。 输出 对于每个s，请输出最大的n，使得对某个字符串a，s=a^n。 提示 本题海量输入，为避免超时，请使用scanf替代cin。
思路： 设字符串s的长度为L=strlen (s+1) ，字符串s的下标从1开始。 首先计算出字符串s中每个前缀的hash函数值， 即h[i] = h[i-1] * base + str[i] - ‘a’ + 1 (1<=i<=L); 利用unsigned long long溢出取模 然后按照长度递增的顺序枚举s中可能存在的相邻子串。 若L%x=0,则说明s中可能存在长度为x且满足相乘关系的相邻子串， 即对于等长子串 s[1…x],s[x+1…2x],s[(n-1)*x+1…l] 如果h[x] = h[x+1…2x] = … = h[(n-1)*x+1…l] 其中，s[l…r]的hash值为 h[r] - h[l - 1] * k^(r - l + 1) k的n次方可以用一个数组p来存， 将上式改写为: h[r] - h[l - 1] * p[r - l + 1] 则相乘关系成立，即s为连续n个子串a，s=a^n。 由于此时子串长度x是最小的，因此次幂n=L/x为最大， n即为问题的解。
字符串哈希讲解
代码：
#include<iostream> #include<string.h> using namespace std; typedef unsigned long long ULL; const int N = 1000010,base = 131; char str[N]; ULL h[N],p[N]; int len; ULL get(int l,int r)//获得 l 到 r 的 hash 值 { return h[r] - h[l - 1] * p[r - l + 1]; } bool check(int x)//若所有长度为 x 的相邻子串对应的散列函数值相等，则返回 true；否则返回 false { for(int i = x*2 ;i <= len;i += x) if(h[x] != get(i-x+1,i)) return false; return true; } int main() { while(~scanf("%s",str + 1)) { len = strlen(str + 1); if(len == 1&&str[1] == '.') return 0; h[0] = 0,p[0] = 1; for(int i = 1;i <= len;i ++ ) { h[i] = h[i-1] * base + str[i] - 'a' + 1; p[i] = p[i-1] * base; } for(int i = 1;i <= len;i ++ ) if(len%i == 0 && check(i)) { printf("%d\n",len/i); break; } } return 0; }