公共因子 Time Limit: 1000MS Memory limit: 65536K 題目描述 假設字符串也有因數，一個字符串為s1，然後可以由n個字符串s2來表示，則稱s2是s1的因數。 如“ac”是“acac”的因數。 給兩個字符串，求它們的公因數有多少個。 輸入 多組數據，給定兩個字符串,s1,s2。長度不超過100000，並且不含空格。 輸出 每組數據一行，公因數有多少個。 示例輸入 acac ac aaa aa 示例輸出 1 1 提示 先對長度求公共因子 [cpp] #include <stdio.h> #include <string.h> #include <math.h> int a[1000000],b[1000000]; char s1[1000000],s2[1000000],s3[1000000]; int main() { int i,j,n,m,s,t,l1,l2,top,top1,x; while(scanf("%s %s",s1,s2)!=EOF) { l1=strlen(s1); s=0; for(i=1,top=0;i<=l1;i++) { if(l1%i==0) { a[top++]=i; } } for(i=0,top1=0;i<=top-1;i++) { for(j=0;j<=a[i]-1;j++) { s3[j]=s1[j]; } if(a[i]==l1) { b[top1++]=a[i]; continue; } for(j=a[i];j<=l1-1;j+=a[i]) { for(x=0;x<=a[i]-1;x++) { if(s3[x]!=s1[j+x]) { break; } } if(x!=a[i]) { break; } } if(j==l1) { b[top1++]=a[i]; } } l2=strlen(s2); for(i=0;i<=top1-1;i++) { if(l2%b[i]==0) { for(j=0;j<=l2-1;j+=b[i]) { for(x=0;x<=b[i]-1;x++) { if(s1[x]!=s2[j+x]) { break; } } if(x!=b[i]) { break; } } if(j==l2) { s++; } } } printf("%d\n",s); } return 0; }
