ACM (TJU) : 1630


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

char a [1000];
char b [1000];
int len_a;
int len_b;

int commonA (int x)
{
    int count = 0;

    for ( int i = x, j = 0; i < len_a; i++, j++ ) {
        if ( j < len_b && a [i] == b [j] )
            count++;
    }

    return count;
}

int commonB (int x)
{
    int count = 0;

    for ( int i = x, j = 0; i < len_b; i++, j++ ) {
        if ( j < len_b && b [i] == a [j] )
            count++;
    }

    return count;
}

int GCD (int x, int y)
{
    if ( y == 0 )
        return x;
    return GCD (y, x % y);
}

int main ()
{
    while ( scanf ("%s", a) ) {
        if ( !strcmp (a, "-1") )
            return 0;

        scanf ("%s", b);

        len_a = strlen (a);
        len_b = strlen (b);
        int max = 0;

        for ( int i = 0; a [i] != 0; i++ ) {
            int temp = commonA (i);
            if ( temp > max )
                max = temp;
        }

        for ( int i = 0; b [i] != 0; i++ ) {
            int temp = commonB (i);
            if ( temp > max )
                max = temp;
        }

        int total_len = len_a + len_b;
        int gcd = GCD (max * 2, total_len);
        int nomin = (max * 2) / gcd;
        int domin = total_len / gcd;

        if ( nomin == 0 || (nomin == 1 && domin == 1) )
            printf ("appx(%s,%s) = %d\n", a, b, nomin);
        else
            printf ("appx(%s,%s) = %d/%d\n", a, b, nomin, domin);

    }

    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s