2013年8月16日 星期五

2013/8/16 POJ 3080 Blue Jeans

// http://poj.org/problem?id=3080
#include <iostream>
#include <cstdio>
using namespace std;
char p[10][60]; int m; int ansi = 0; char ans[60];
bool check(int i, int j)
{

    for(int k = 1; k < m; k++)
    {
        int flag = 0;
        for(int op = 0; op < 60; op++)
        {
            for(int u = 0; u < j ; u++)
                if( op + u >= 60 || p[k][op+u] != p[0][i+u] ) goto abc;

            flag = 1;
            abc:;
       
            if( flag == 1 ) break;
        }
        if( flag == 0 ){  return 0; }
    }
    return 1;
}
bool cmp(int i, int j)
{
    for(int op = 0; op < j; op++)
        if( ans[op] > p[0][i+op] ) return 1;
        else if( ans[op] < p[0][i+op] ) return 0;

    return 0;
}
int main()
{
    int n; scanf("%d", &n);

    while( n-- )
    {
         scanf("%d", &m);

        for(int i = 0; i < m; i++)
            scanf("%s", p[i]);

        ansi = 0;
        for(int i = 0; i < 60; i++)
            for(int j = 1; i+j <= 60; j++)
                if( check( i, j)==true )
                {

                    if( ansi < j )
                    {
                        ansi = j;
                        for(int k = 0; k < j; k++)
                            ans[k] = p[0][i+k];
                    }
                    else if( ansi == j )
                    {
                        if( cmp( i, j) == 1 )
                            for(int k = 0; k < j; k++)
                                ans[k] = p[0][i+k];
                    }
                }
        if( ansi < 3 ) printf("no significant commonalities\n");
        else
        {
            for(int i = 0; i < ansi; i++) printf("%c", ans[i]);
            printf("\n");
        }
    }
}

沒有留言:

張貼留言