1580.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

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

int gcd( int a, int b )
{
        int c;
        if( a == 0 ) return b;
        while( b )
        {
                 c = a%b;
                 a = b;
                 b = c;
         }
         
         return a;
}

char w1[1000],w2[1000];

int main()
{
        int i, j, k, h, l1,l2, ans, g, temp;
        
        while( 1 )
        {
                scanf( "%s", w1 );
                if( w1[0] == '-' && w1[1] == '1' && w1[2] == '\0' ) break;
                scanf( "%s", w2 );
                
                ans = -1;
                for( ans=0,k=0; w2[k]; k++ )
                for( h=0; w1[h]; h++ )
                {
                        for( temp=0,i=h,j=k; w1[i] && w2[j]; i++, j++ )
                        if( w1[i] == w2[j] ) temp++;

                        if( temp > ans ) ans = temp;
                }
                
                l1 = strlen( w1 );
                l2 = strlen( w2 );
                g = gcd( ans*2, l1+l2 );
                
                printf( "appx(%s,%s) = ", w1, w2 );
                if( !ans || ans*2 == l1+l2 ) printf( "%d\n", ans * 2 / ( l1+l2 ) );
                else printf( "%d/%d\n", ans*2/g, ( l1+l2 ) / g );
       }
        return 0;
}