1947391_ac_0ms_60k.c

北大大牛代码 1240道题的原代码 超级权威

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

int cmp(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

int get_gcd(int a, int b)
{
    int r;
    if (b == 0)  return a;
    for (r = a % b; r != 0; r = a % b)
    {
        a = b;
        b = r;
    }
    return b;
}

int main()
{ 
   int i, j, len1, len2, m, len, no, tmp, max;
   int d[10][10], a1[10];
   char str1[10], str2[10];
   
   while(scanf("%s",str1)==1&&strcmp(str1,"-1")!=0)
   { 
      scanf("%s",str2);
	  printf("appx(%s,%s) = ",str1,str2);
      len1 = strlen(str1);
      len2 = strlen(str2);
      for(i = 0; i < 10; i++)
			  d[i][0] = d[0][i] = 0;
      for(i = 1; i <= len1; i++)
         for(j = 1; j <= len2; j++)
            if(str1[i-1] == str2[j-1])
               d[i][j] = d[i-1][j-1] + 1;
            else
               d[i][j] = d[i-1][j] > d[i][j-1] ? d[i-1][j] : d[i][j-1];
			m = 0;len = d[len1][len2];
			if(len == 0)
			{
				printf("0\n");
				continue;
			}
			if(len*2==len1+len2)
			{
				printf("1\n");
				continue;
			}
	  for(i = len1; i > 0;)
		  for(j = len2; j > 0;)
			  if(d[i][j] == d[i-1][j-1])
				  i--;
			  else 
				  if(d[i][j] == d[i][j-1])
					  j--;
				  else
				  {
					  a1[m] = i-j;
					  m++;
					  i--;j--;
				  }
	   qsort(a1,len,sizeof(a1[0]),cmp);
	   max = -10000;
	   for(i = 0; i < len;)
	   {
		   tmp = a1[i++];
		   no = 1;
		   while(i<len&&a1[i]==tmp)
		   {
			   i++;
			   no++;
		   }
		   if(no > max)
			   max = no;
	   }
	   tmp = get_gcd(max*2,len1+len2);
	   printf("%d/%d\n",max*2/tmp,(len1+len2)/tmp);
   }
   return 1;
}