公共因子
Time Limit: 1000MS Memory limit: 65536K
题目描述
题目链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1465
假设字符串也有因数，一个字符串为s1，然后可以由n个字符串s2来表示，则称s2是s1的因数。
如“ac”是“acac”的因数。
给两个字符串，求它们的公因数有多少个。
输入
多组数据，给定两个字符串,s1,s2。长度不超过100000，并且不含空格。
输出
每组数据一行，公因数有多少个。
示例输入
acac
ac
aaa
aa
示例输出
1
1
提示
解题思路：暴力搜索方法解题，公共因子长度一定是第一个字符串的整数倍，第一次剪枝找出所有可能（注意是“可能”）满足第一个字符串条件的因子的长度，保存在数组f1中；第二次剪枝遍历f1数组，找出所有满足第一个字符串的因子，记录它们的长度，保存在数组g1中；遍历g1数组，找出所有满足第二个字符串的公共因子的因子，用count记录所有满足条件因子的个数，count就是最后的结果，经过三次剪枝，最终可以得到答案。
代码：
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int main()
{
char f[],g[];
while(scanf("%s%s",f,g)!=EOF)
{
int lenf=strlen(f),leng=strlen(g);
int f1[]={},g1[]={},t=-,s=-;
int i,j,k;
for(i=;i<=lenf;i++)
if(lenf%i==)f1[++t]=i;
int flag;
for(i=;i<=t-;i++)
{
char zhong[];
for(j=;j<=f1[i]-;j++)
zhong[j]=f[j];
for(j=f1[i];f[j]!='\0';j+=f1[i])
{
flag=;
for(k=;k<=f1[i]-;k++)
if(f[j+k]!=zhong[k])
{
flag=;
break;
}
if(flag==)break;
}
if(j==lenf)g1[++s]=f1[i];
}
g1[++s]=lenf;
int count=;
for(i=;i<=s;i++)
{
if(leng%g1[i]==)
{
for(j=;g[j]!='\0';j+=g1[i])
{
flag=;
for(k=;k<=g1[i]-;k++)
{
if(g[k+j]!=f[k])
{
flag=;
break;
}
}
if(flag==)break;
}
if(j==leng)count++;
}
}
cout<<count<<endl;
}
return ;
}