poj 1580 String Matching【gcd辗转相除法】

开始想用类似“错车”的思路去解决，但是发现不是太好着手，还是选用首字母定位的方法去解决的

题意：现定义两个仅由大写字母组成的字符串的匹配程度如下：将某一字符串的首字符与另一字符串的某一字符对齐，然后后面的字符也一一对齐，直至某一字符串的串尾为止。对于每一组对齐的两个字符，若这两个字符相等，则计数。最后计算这个计数的2倍，与两串总长度的最大比值。

如果说这题最大的收获就是，两种方法的辗转相除法求gcd

AC的代码：

#include <stdio.h>
#include <string.h>


/*//辗转相除法的递归写法
int gcd(int a,int b)
{
if(!b) return a;
return gcd(b,a%b);
}
*/


int gcd(int a, int b)
{//辗转相除法
    while (b%a)
    {
		int t=a;
		a=b%a;
		b=t;
    }
    return a;
}

void appx(char * wo1,char * wo2)
{
	if(!strcmp(wo1,wo2))
	{
		printf("appx(%s,%s) = 1\n",wo1,wo2);
		return;
	}

	//值已经传进来了
	int len1=strlen(wo1),len2=strlen(wo2);
	int count=0;
	
	int i,j,max,common=0;
	//枚举word1和word2的首字母
	for(i=0;i<len1;i++)
	{
		for(j=0;j<len2;j++)
		{
			max=0;
			for (int i1=i,j1=j;i1<len1 && j1<len2;++i1,++j1)
				if (wo1[i1]==wo2[j1]) 
					++max;

			if (common<max) 
				common=max;
		}
	}

	if(common==0)
	{
		printf("appx(%s,%s) = 0\n",wo1,wo2);
		return;
	}

	int molecular=common*2;//分子
	int denominator=len1+len2;//分母

	int g=gcd(molecular,denominator);

	printf("appx(%s,%s) = %d/%d\n",wo1,wo2,molecular/g,denominator/g);
}


int main()
{
	char word1[105],word2[105];
	while(scanf("%s",word1))
	{
		if(!strcmp(word1,"-1"))
			return 0;
		
		scanf("%s",word2);
		
		appx(word1,word2);
	}
	
	return 0;
}