Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
0ms水过,附代码(慎入),另求高效算法~//p1580 g++ AC 0ms #include <stdio.h> #include <string.h> #define M 100010 char sa[M], sb[M]; int la, lb; int solve() { la = strlen(sa); lb = strlen(sb); int maxlen = 0; for (int i = 0; i < la; ++ i) { for (int j = 0; j < lb; ++ j) { int len = 0; for (int i1 = i, j1 = j; i1 < la && j1 < lb; ++ i1, ++ j1) { if (sa[i1] == sb[j1]) { ++ len; } } if (maxlen < len) { maxlen = len; } } } return maxlen<<1; } int gcd(int a, int b) { return b?gcd(b,a%b):a; } void print() { int res = solve(); int len = la+lb; printf("appx(%s,%s) = ",sa,sb); if (!res) { puts("0"); } else if (res == len) { puts("1"); } else { int g = gcd(res, len); printf("%d/%d\n", res/g, len/g); } } int main() { while (scanf("%s", sa) && strcmp(sa,"-1") && scanf("%s", sb)) { print(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator