Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

n=60、m=10,纯暴力也就O(m*n^3),0ms

Posted by uuuouou at 2014-09-05 00:17:16 on Problem 3080
#include <stdio.h>
#include <string.h>

int main()
{
    int test, n, i, j, k, start, len, flag;
    char s[10][61], c;
    
    scanf("%d", &test);
    while(test--){
        scanf("%d", &n);
        while(getchar() != '\n') ;
        for(i = 0; i < n; ++i) gets(s[i]);
        
        start = len = 0;
        for(k = 3; k <= 60; ++k){
            for(i = 0; i+k <= 60; ++i){
                c = s[0][i+k];
                s[0][i+k] = '\0';
                flag = 1;
                for(j = 1; j < n && flag; ++j){
                    if(NULL == strstr(s[j], s[0]+i)) flag = 0;
                }
                if(flag){
                    if(k > len){
                        start = i;
                        len = k;
                    }
                    else if(strncmp(s[0]+i, s[0]+start, k) < 0){
                        start = i;
                        len = k;
                    }
                }
                s[0][i+k] = c;
            }
        }
        
        if(len < 3) puts("no significant commonalities");
        else{
            s[0][start+len] = '\0';
            puts(s[0]+start);
        }
    }
    
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator