Common Divisors CodeForces - 182D || kmp最小循环节

Common Divisors CodeForces - 182D

思路：用kmp求next数组的方法求出两个字符串的最小循环节长度（http://blog.csdn.net/acraz/article/details/47663477，http://www.cnblogs.com/chenxiwenruo/p/3546457.html），然后取出最小循环节，如果最小循环节不相同答案就是0，否则求出各个字符串含有的最小循环节的数量，求这两个数量的公因数个数（也就是最大公因数的因子个数）就是答案。

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 char s1[],s2[];

 char c[],d[];

 int f[];

 int m1,m2,ans;

 int getf(char *P,int *f,int& m)

 {

     int j=f[]=-,i=;

     while(i<m)

     {

         while(j>=&&P[i]!=P[j])    j=f[j];

         ++j;++i;

         f[i]=j;

     }

     return m%(m-f[m])==?m-f[m]:m;

 }

 int gcd(int a,int b)

 {

     int t;

     while(b!=)

     {

         t=a;

         a=b;

         b=t%b;

     }

     return a;

 }

 int main()

 {

     int i,p,t;

     scanf("%s%s",s1,s2);

     m1=strlen(s1);

     m2=strlen(s2);

     int a=getf(s1,f,m1);

     int b=getf(s2,f,m2);

     strncpy(c,s1,a);

     strncpy(d,s2,b);

     if(strcmp(c,d)!=)

         printf("");

     else

     {

         p=gcd(m1/a,m2/b);

         t=(int)sqrt(p+0.5);

         for(i=;i<=t;i++)

             if(p%i==)

                 ans+=;

         if(t*t==p)    ans--;

         printf("%d",ans);

     }

     return ;

 }