http://codeforces.com/problemset/problem/182/D

  1. 用KMP求出最短重复子串(前缀)
  2. 由于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;
}

Comments

comments powered by Disqus