java實現字符串匹配問題之求最大公共子串
來源：程序員人生 發布時間：2014-09-11 11:02:40 閱讀次數：3484次
轉載請注明出處：http://blog.csdn.net/xiaojimanman/article/details/38924981
最近在項目工作中有一個關于文本對比的需求，經過這段時間的學習，總結了這篇博客內容：求兩個字符串的最大公共子串。
算法思想：基于圖計算兩字符串的公共子串。具體算法思想參照下圖：
輸入字符串S1：achmacmh 輸入字符串S2：macham
1）第a步，是將字符串s1,s2分別按字節拆分，構成一個二維數組；
2）二維數組中的值如b所示，比如第一行第一列的值表示字符串s2和s1的第一個字節是否相等，若相等就是1，否則就是0，最終產生b所示的二維數組；
3）分別求二維數組中斜線上的公共因子（斜線為元素a右下角值，即a[i][j]的下一個元素是a[i+1][j+1]；公共因子為1所在的位置構成的字符串）；
4）對所有公共因子排序，返回最大的公共因子的值。
具體的實現代碼如下所示：
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"));
}
}
程序最終執行結果是：
對于兩個文件的比對個人認為可以參照這種算法思想（自己現在并為實現），在日后的博客中將會寫到。
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
