本文實例講述了java實現求兩個字符串最大公共子串的方法。分享給大家供大家參考，具體如下：
最近在項目工作中有一個關于文本對比的需求，經過這段時間的學習，總結了這篇博客內容：求兩個字符串的最大公共子串。
算法思想：基于圖計算兩字符串的公共子串。具體算法思想參照下圖：
輸入字符串S1：achmacmh 輸入字符串S2：macham
- 第a步，是將字符串s1,s2分別按字節拆分，構成一個二維數組；
- 二維數組中的值如b所示，比如第一行第一列的值表示字符串s2和s1的第一個字節是否相等，若相等就是1，否則就是0，最終產生b所示的二維數組；
- 分別求二維數組中斜線上的公共因子（斜線為元素a右下角值，即a[i][j]的下一個元素是a[i+1][j+1]；公共因子為1所在的位置構成的字符串）；
- 對所有公共因子排序，返回最大的公共因子的值。
具體的實現代碼如下所示：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
package cn.lulei.compare; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; public class StringCompare { private int a; private int b; public String getMaxLengthCommonString(String s1, String s2) { if (s1 == null || s2 == null) { return null; } a = s1.length();//s1長度做行 b = s2.length();//s2長度做列 if(a== 0 || b == 0) { return ""; } //設置匹配矩陣 boolean [][] array = new boolean[a][b]; for (int i = 0; i < a; i++) { char c1 = s1.charAt(i); for (int j = 0; j < b; j++) { char c2 = s2.charAt(j); if (c1 == c2) { array[i][j] = true; } else { array[i][j] = false; } } } //求所有公因子字符串，保存信息為相對第二個字符串的起始位置和長度 List<ChildString> childStrings = new ArrayList<ChildString>(); for (int i = 0; i < a; i++) { getMaxSort(i, 0, array, childStrings); } for (int i = 1; i < b; i++) { getMaxSort(0, i, array, childStrings); } //排序 sort(childStrings); if (childStrings.size() < 1) { return ""; } //返回最大公因子字符串 int max = childStrings.get(0).maxLength; StringBuffer sb = new StringBuffer(); for (ChildString s: childStrings) { if (max != s.maxLength) { break; } sb.append(s2.substring(s.maxStart, s.maxStart + s.maxLength)); sb.append(" "); } return sb.toString(); } //排序，倒敘 private void sort(List<ChildString> list) { Collections.sort(list, new Comparator<ChildString>(){ public int compare(ChildString o1, ChildString o2) { return o2.maxLength - o1.maxLength; } }); } //求一條斜線上的公因子字符串 private void getMaxSort(int i, int j, boolean [][] array, List<ChildString> sortBean) { int length = 0; int start = j; for (; i < a && j < b; i++,j++) { if (array[i][j]) { length++; } else { sortBean.add(new ChildString(length, start)); length = 0; start = j + 1; } if (i == a-1 || j == b-1) { sortBean.add(new ChildString(length, start)); } } } //公因子類 class ChildString { int maxLength; int maxStart; ChildString(int maxLength, int maxStart){ this.maxLength = maxLength; this.maxStart = maxStart; } } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out.println(new StringCompare().getMaxLengthCommonString("achmacmh", "macham")); } } |
程序最終執行結果是：
對于兩個文件的比對個人認為可以參照這種算法思想（自己現在并為實現），在日后的博客中將會寫到。
上述實現過程中，用數組保存了所有的公共子串信息，然后排序取最大的子串，這種做法如果只是求最大子串的話，算法就不是很合理，因此做了如下修改，List只保存當前計算中最大的子串，具體實現如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
/** *@Description: 字符串比較 */package com.lulei.test; import java.util.ArrayList; import java.util.List; public class StringCompare { private int a; private int b; private int maxLength = -1; public String getMaxLengthCommonString(String s1, String s2) { if (s1 == null || s2 == null) { return null; } a = s1.length();//s1長度做行 b = s2.length();//s2長度做列 if(a== 0 || b == 0) { return ""; } //設置匹配矩陣 boolean [][] array = new boolean[a][b]; for (int i = 0; i < a; i++) { char c1 = s1.charAt(i); for (int j = 0; j < b; j++) { char c2 = s2.charAt(j); if (c1 == c2) { array[i][j] = true; } else { array[i][j] = false; } } } //求所有公因子字符串，保存信息為相對第二個字符串的起始位置和長度 List<ChildString> childStrings = new ArrayList<ChildString>(); for (int i = 0; i < a; i++) { getMaxSort(i, 0, array, childStrings); } for (int i = 1; i < b; i++) { getMaxSort(0, i, array, childStrings); } StringBuffer sb = new StringBuffer(); for (ChildString s: childStrings) { sb.append(s2.substring(s.maxStart, s.maxStart + s.maxLength)); sb.append(" "); } return sb.toString(); } //求一條斜線上的公因子字符串 private void getMaxSort(int i, int j, boolean [][] array, List<ChildString> sortBean) { int length = 0; int start = j; for (; i < a && j < b; i++,j++) { if (array[i][j]) { length++; } else { //直接add，保存所有子串，下面的判斷，只保存當前最大的子串 //sortBean.add(new ChildString(length, start)); if (length == maxLength) { sortBean.add(new ChildString(length, start)); } else if (length > maxLength) { sortBean.clear(); maxLength = length; sortBean.add(new ChildString(length, start)); } length = 0; start = j + 1; } if (i == a-1 || j == b-1) { //直接add，保存所有子串，下面的判斷，只保存當前最大的子串 //sortBean.add(new ChildString(length, start)); if (length == maxLength) { sortBean.add(new ChildString(length, start)); } else if (length > maxLength) { sortBean.clear(); maxLength = length; sortBean.add(new ChildString(length, start)); } } } } //公因子類 class ChildString { int maxLength; int maxStart; ChildString(int maxLength, int maxStart){ this.maxLength = maxLength; this.maxStart = maxStart; } } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out.println(new StringCompare().getMaxLengthCommonString("abcdef", "defabc")); } } |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
