SDUT 1465 公共因子
公共因子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;
}
补充：软件开发 , C++ ,
