2013年微软编程之美大赛初赛第二题（博客园居然可以插入代码！！）

描述

对于两个长度相等的字符串，我们定义其距离为对应位置不同的字符数量，同时我们认为距离越近的字符串越相似。例如，“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

解法一：(穷举法）

#include <iostream>
#include <vector>
#include <cstring>
#include <new>

using namespace std;

int main()
{
int T;
scanf("%d",&T);

int x = 1;
while ( x <= T )
{
string s1;
string s2;
int maxDistance = ~(1 << 31);

cin.get();
getline(cin,s1,'\n');
cin.get();
cin >> s2;

// typedef string::size_type chartype;
// chartype pos;

int i = 0;

while ( i <= s1.size() )
{
int cnt = 0;
int j = 0;
while ( j <= s2.size() )
{
if( s1[i + j] != s2[j] )
cnt++;
j++;
}

if ( cnt < maxDistance )
maxDistance = cnt;
i++;
}

printf("Case #%d: %d\n",x,maxDistance);
x++;
}

return 0;
}

在实验室电脑上运行没问题，因为不能提交，所以也求证大数据运行结果如何。

解法二：

 1 #include <iostream>
 2 #include <vector>
 3 #include <cstring>
 4 #include <new>
 5 
 6 using namespace std;
 7 
 8 int main()
 9 {
10     int T;
11     scanf("%d",&T);
12     
13     int x = 1;
14     while ( x <= T )
15     {
16         string words;
17         string s;
18         int maxDistance = ~(1 << 31);
19         
20         cin >> words;
21         cin >> s;
22         
23         typedef string::size_type strtype;
24         strtype pos;
25         int size = s.size();
26         
27         int i = 0;
28         while ( i < size )
29         {
30             strtype index = 0;
31             
32             int cnt = maxDistance;
33             char ch = s[i];
34             
35             pos = words.find(ch,index);
36             
37             while ( pos != string::npos )
38             {
39                 int k = 0;
40                 
41                 if ( pos >= i )
42                 {
43                     string tmp;
44                     tmp = words.substr(pos - i,size );
45                     
46                     int j = 0;
47                     
48                     while ( j < size )
49                     {
50                         if ( tmp[j] != s[j] )
51                             k++;
52                         j++;
53                     }
54                 }
55                 else if (pos + size > words.size() )
56                     break;
57                 else 
58                     goto lable;
59                     
60                 index = pos + 1;
61                 pos = words.find(ch,index);
62                 cnt = (k < cnt) ? k : cnt;
63             }
64             
65             if( cnt < maxDistance )
66                 maxDistance = cnt;
67                 
68             i++;
69         }
70 lable:        
71         printf("Case #%d: %d\n",x,maxDistance);
72         x++;
73     }
74     
75     return 0;
76 }

这个应该是能够通过大数据的。。。（依旧没验证）