现在的位置: 首页 > 综合 > 正文

2013编程之美全国挑战赛初赛第一场 第二题 相似字符串

2018年02月20日 ⁄ 综合 ⁄ 共 984字 ⁄ 字号 评论关闭

时间限制: 4000ms 内存限制: 256MB

描述

对于两个长度相等的字符串,我们定义其距离为对应位置不同的字符数量,同时我们认为距离越近的字符串越相似。例如,“0123”和“0000”的距离为 3,“0123”和“0213”的距离则为 2,所以与“0000”相比,“0213”和“0123”最相似。

现在给定两个字符串 S1 和 S2,其中 S2 的长度不大于 S1。请在 S1 中寻找一个与 S2 长度相同的子串,使得距离最小。

输入

输入包括多组数据。第一行是整数 T,表示有多少组测试数据。每组测试数据恰好占两行,第一行为字符串 S1,第二行为 S2。所有字符串都只包括“0”到“9”的字符。

输出

对于每组测试数据,单独输出一行“Case #c: d”。其中,c 表示测试数据的编号(从 1 开始),d 表示找到的子串的最小距离。

数据范围

1 ≤ T ≤ 100

小数据:字符串长度不超过 1000

大数据:字符串长度不超过 50000

样例输入
3
0123456789
321
010203040506070809
404
20121221
211
样例输出
Case #1: 2
Case #2: 1
Case #3: 1

纠结为神马 用java写能过,而我用C++写 4010ms(总时限4000ms).....

import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner s = new Scanner(System.in);
		int t = s.nextInt(), c = 1;
		s.nextLine();
		while(c<=t) {
			String s1 = s.nextLine();
			String s2 = s.nextLine();
			System.out.println("Case #"+ (c++) + ": " + func(s1,s2));
		}
	}
	public static int func(String s1, String s2) {
		int result = s2.length();
		for (int i=0; i<=s1.length() - s2.length(); i++) {
			int count = 0;
			for (int j=0; j<s2.length(); j++){
				if(s1.charAt(i+j) !=s2.charAt(j)) count++;
			}
			if (count < result) result = count;
		}
		return result;
	}
}

抱歉!评论已关闭.