注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

长风明志的博客

不要也不能做下一个谁,应该且可以做第一个自己

 
 
 

日志

 
 

【2013编程之美初赛】 相似字符串  

2013-04-13 18:32:08|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
如果不考虑大数据情况,只求AC,这题非常简单。。。

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

由于技术问题,导致比赛初期网站难以访问,我们深感抱歉。因此,本场比赛延长半小时,晋级复赛名额增加300(总时长2.5小时,本场比赛前800晋级复赛)。

描述

对于两个长度相等的字符串,我们定义其距离为对应位置不同的字符数量,同时我们认为距离越近的字符串越相似。例如,“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
小数据:
状态: Accepted
大数据:
状态: Time Limit Exceeded
源代码
#include <string>
#include <iostream>
#include <vector>
#define MAXSIZE 65536
using namespace std;
int main()
{
    int T;
	string A,B;
	int distance;
	vector<int> vecResult;
	cin>>T;
	while(T--)
	{
		cin>>A;
		cin>>B;
        distance=MAXSIZE;
		for(int i=0;i<=A.size()-B.size();i++)
		{
			int tempDistance=0;
			for(int j=0;j<B.size();j++)
			{
                if(A[i+j]!=B[j])
				{
					tempDistance++;
				}
			}
			if(tempDistance<distance)
				distance=tempDistance;
		}
		vecResult.push_back(distance);
	}
	for(int i=0;i<vecResult.size();i++)
	{
		cout<<"Case #"<<i+1<<": "<<vecResult[i]<<endl;
	}
	return 0;
}
  评论这张
 
阅读(477)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017