sdut 1465 公共因子

公共因子

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 ;

 }

巴特西