相似字符串
编程之美 2013 全国挑战赛 初赛第一场 题目二 相似字符串
题目二 相似字符串
时间限制: 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 表示找到的子串的最小距离。
数据范围
样例输入
3
0123456789
321
010203040506070809
404
20121221
211
样例输出
Case #1: 2
Case #2: 1
Case #3: 1
解题思路
这道题其实不复杂，结果我很蛋疼的用了一个字符串近似匹配的 DP 算法，结果果然悲剧了……在这里就只好读读大神们的代码，看看有什么给力的解法。
首先设两个字符串分别为 s1 和 s2，它们的长度为 m 和 n ，其中 m ≥ n 。
最简单的方法是直接暴力字符串匹配，就是尝试将每个 s 1 i … i + n 和 s 2 0 … n 进行匹配（排名第二的 Tripod2K 就是这么过的），不过需要注意 如果距离已经大于当前的最小距离了，就不必继续匹配下去了 ，否则是会悲剧的。核心算法为：
1 int min = n; // 初始最小距离为 n
2 for ( int i = 0 ; i <= m-n; i++ ) {
3 int dis= 0 ;
4 // 尝试匹配 s1[i...i+n] 和 s2
5 for ( int j = 0 ; j < n; j++ ) {
6 if (s1[i + j] != s2[j]) dis++ ;
7 if (dis >= min) {
8 // 这里 dis 已经超过 min 了，再继续匹配下去也没有什么用
9 break ;
10 }
11 }
12 if (dis < min) min = dis;
13 if (min == 0 ) {
14 // min 到达了 0，已经不可能更小了，也不必再匹配下去了
15 break ;
16 }
17 }
完整的代码为：（链接在 这里 ）
View Code
1 // source here
2 import java.util.Scanner;
3
4 public class Main {
5 public static void main(String args[]){
6 Scanner in = new Scanner(System.in);
7 int t = in.nextInt();
8 byte [] s1 = new byte [60000 ];
9 byte [] s2 = new byte [60000 ];
10 for ( int i = 1; i <= t; i++ ){
11 s1 = in.next().getBytes();
12 s2 = in.next().getBytes();
13 int d = distance(s1, s2);
14 System.out.println("Case #" + i + ": " + d);
15 }
16 }
17
18 private static int distance( byte [] s1, final byte [] s2){
19 int l1 = s1.length;
20 int l2 = s2.length;
21 int result = l2;
22 for ( int i = 0; i <= l1 - l2; ++ i){
23 int tmp= 0 ;
24 for ( int j = 0; j < l2; ++ j){
25 if (s1[i + j] != s2[j]) tmp++ ;
26 if (tmp >= result) break ;
27 }
28 if (tmp < result) result = tmp;
29 if (tmp == 0) break ;
30 }
31 return result;
32 }
33 }
还有排名第四的 chaozicen 的算法，则比较巧妙。现在假设 s1="010203040506070809"，s2="404"，首先对 s1 进行预处理，标记出每个字符出现的索引，得到下面的表格：
字符 出现的索引 '0' 0,2,4,6,8,10,12,14,16 '1' 1 '2' 3 '3' 5 '4' 7 '5' 9 '6' 11 '7' 13 '8' 15 '9' 17然后在读取 s2 的每个字符时，根据表格在一个长为 n 的 int 数组 ans 上进行标记 s2[0] 出现的位置。例如现在 s2[0] = '4'，表格中字符 '4' 对应的索引只有 7，那么令 ans[7-0]++；然后读取 s2[1]='0'，表格中字符 '0' 对应的索引有 0,2,4,6,8,10,12,14 和 16，那么就令 ans[0-1]、ans[2-1]、ans[4-1]、ans[6-1]、ans[8-1]、ans[10-1]、ans[12-1]、ans[14-1] 和 ans[16-1] 均加一；最后读取 s2[2] = '4'，令 ans[7-2]++。最后得到的 ans 数组如下所示：
ans = {0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0 ,1, 0, 1};
那么这个 ans 表示什么呢？ans[i] 表示 s 1 i … i + n 与 s 2 0 … n 中 完全相同 的字符的个数，最后只要统计 ans 中最大的那个，就表示距离最小。
下面是 chaozicen 的源代码，链接在 这里 ：
View Code
1 // source here
2 #include<iostream>
3 #include< string >
4 using namespace std;
5 int num[ 10 ][ 60000 ],ans[ 60000 ];
6 int main()
7 {
8 int T,n,i,k,j,s,l1,l2,anss,t;
9 string s1,s2;
10 cin>> T;
11 t= 1 ;
12 while (T>= t)
13 {
14 ++ t;
15 cin>>s1;cin>> s2;
16 l1=s1.length(); l2= s2.length();
17 for (i= 0 ;i< 10 ;++i) num[i][ 0 ]= 0 ;
18 for (i= 0 ;i<l1;++ i)
19 {
20 k=s1[i]- ' 0 ' ;
21 ++num[k][ 0 ];
22 num[k][num[k][ 0 ]]= i;
23 ans[i]= 0 ;
24 }
25 for (i= 0 ;i<l2;++ i)
26 {
27 k=s2[i]- ' 0 ' ;
28 for (j= 1 ;j<=num[k][ 0 ];++ j)
29 {
30 if (num[k][j]-i>= 0 )
31 ans[num[k][j]-i]++ ;
32 }
33 }
34 anss= 0 ;
35 for (i= 0 ;i<l1-l2+ 1 ;++ i)
36 if (ans[i]>anss) anss= ans[i];
37 anss=l2- anss;
38 cout<< " Case # " <<t- 1 << " : " <<anss<< endl;
39 }
40 return 0 ;
41 }
题目三是一个好复杂的搜索，我根本没仔细看，题目一我也没搞明白怎么个是最优策略。
作者： CYJB
出处： http://www.cnblogs.com/cyjb/
GitHub： https://github.com/CYJB/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
分类: Algirithm
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息