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

0ms水过,附代码(慎入),另求高效算法~

Posted by zerocpp at 2011-04-08 00:37:17 on Problem 1580 and last updated at 2011-04-08 00:40:51
//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:
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