Codeforces Round #117 (Div. 2) / 182D Common Divisors (KMP 前缀)
http://codeforces.com/problemset/problem/182/D
- 用KMP求出最短重复子串(前缀)
- 由于s1和s2的最短子串的重复次数的gcd可视为两个串的最长重复子串,而最长重复子串的"因子子串"必然也是两个串的重复子串,所以求出gcd的因子个数即可。
/*30ms,600KB*/
const int mx = 100005;
char s1[mx], s2[mx];
int f[mx];
int get_fail(char *p)
{
f[0] = f[1] = 0;
int i, j;
for (i = 1; p[i]; ++i)
{
j = f[i];
while (j && p[i] != p[j]) j = f[j];
f[i + 1] = (p[i] == p[j] ? j + 1 : 0);
}
return i % (i - f[i]) ? i : i - f[i]; /// i当字符串长度看
}
int cnt_divisor(int n)
{
int sqrtn = sqrt((double)n), i, cnt = 0;
Forr(i, 1, sqrtn + 1) if (n % i == 0) cnt += 2;
if (sq(sqrtn) == n) --cnt;
return cnt;
}
int main()
{
gets(s1), gets(s2);
int len1 = strlen(s1), len2 = strlen(s2);
int minpre1 = get_fail(s1), minpre2 = get_fail(s2);
if (minpre1 == minpre2 && strncmp(s1, s2, minpre1) == 0)
PI(cnt_divisor(__gcd(len1 / minpre1 , len2 / minpre1)));
else puts("0");
return 0;
}