CF 182D Common Divisors(KMP最短循环节，循环周期)

链接：

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

题目大意：

假设字符串也有因数，一个字符串S的因数是a，当且仅当S是由k个a连续组成的。 例如S="abababab"， 那么"ab"和"abab"都是S的因子。

给两个字符串，求它们的公因数有多少个。

分析总结：

先看看一个数的因子有什么性质。

如果知道了一个最小因子，那么就可以利用这个最小因子求出一个字符串的所有因子。

例如，假设S="abababab", len = |S| = 8， 最小因子为A="ab", minlen = |A| = 2, 除了这个最小因子之外，可以发现S的所有因子长度x必须满足len%x==0，并且，还要再满足x%minlen==0。 “abab”就是S的另外一个因子，它满足这个要求。

利用这个性质，就可以解决这道题了。

首先，分别利用kmp的next数组可以求出两个字符串的最小因数。然后用其中一个去匹配另一个，每次可以得到一个当前已匹配长度j，根据这个j，利用上述性质，如果同时满足两个字符串的因子要求，那么就是他们的一个公因子了。具体看代码。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

typedef long long int64;
const int MAXN = 100005;
char S[MAXN], T[MAXN];
int  f1[MAXN],f2[MAXN];
bool vis[MAXN];

void getNext(char* P, int* f){
    int n=strlen(P);
    f[0]=f[1]=0;
    for(int i=1; i<n; ++i){
        int j=f[i];
        while(j && P[i]!=P[j]) j=f[j];
        f[i+1] = P[i]==P[j]?1+j:0;
    }
}

int64 find(char* S,char* P,int* f1,int* f2){
    getNext(P,f1);
    getNext(S,f2);
    memset(vis, 0, sizeof(vis));

    int m=strlen(P);
    int n=strlen(S);

    int mp=m%(m-f1[m])?m:(m-f1[m]);
    int ms=n%(n-f2[n])?n:(n-f2[n]);

    int64 cnt=0;
    int j=0;
    for(int i=0; i<n; ++i){
        while(j && S[i]!=P[j]) j=f1[j];
        if(S[i] == P[j]) ++j;
        if(j && !vis[j]){
            if(m%j==0 && n%j==0 && (i+1)%ms==0 && j%mp==0 && j%ms==0){ // 是否满足公因子性质
                ++cnt;
                vis[j]=true;
            }
        }
    }
    return cnt;
}

int main(){
    scanf("%s %s",S,T);
    cout << find(S,T,f1,f2) << endl;
    return 0;
}

—— 生命的意义，在于赋予它意义士。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)