java實(shí)現(xiàn)字符串匹配求兩個(gè)字符串的最大公共子串
更新時(shí)間：2016年10月25日 10:16:48 作者：xiaojimanman
這篇文章主要介紹了java實(shí)現(xiàn)求兩個(gè)字符串最大公共子串的方法，詳細(xì)的描述了兩個(gè)字符串的最大公共子串算法的實(shí)現(xiàn),需要的朋友可以參考下
本文實(shí)例講述了java實(shí)現(xiàn)求兩個(gè)字符串最大公共子串的方法。分享給大家供大家參考，具體如下：
最近在項(xiàng)目工作中有一個(gè)關(guān)于文本對(duì)比的需求，經(jīng)過這段時(shí)間的學(xué)習(xí)，總結(jié)了這篇博客內(nèi)容：求兩個(gè)字符串的最大公共子串。
算法思想：基于圖計(jì)算兩字符串的公共子串。具體算法思想?yún)⒄障聢D：
輸入字符串S1：achmacmh 輸入字符串S2：macham
- 第a步，是將字符串s1,s2分別按字節(jié)拆分，構(gòu)成一個(gè)二維數(shù)組；
- 二維數(shù)組中的值如b所示，比如第一行第一列的值表示字符串s2和s1的第一個(gè)字節(jié)是否相等，若相等就是1，否則就是0，最終產(chǎn)生b所示的二維數(shù)組；
- 分別求二維數(shù)組中斜線上的公共因子（斜線為元素a右下角值，即a[i][j]的下一個(gè)元素是a[i+1][j+1]；公共因子為1所在的位置構(gòu)成的字符串）；
- 對(duì)所有公共因子排序，返回最大的公共因子的值。
具體的實(shí)現(xiàn)代碼如下所示：
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長(zhǎng)度做行
b = s2.length();//s2長(zhǎng)度做列
if(a== 0 || b == 0) {
return "";
}
//設(shè)置匹配矩陣
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;
}
}
}
//求所有公因子字符串，保存信息為相對(duì)第二個(gè)字符串的起始位置和長(zhǎng)度
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("\n");
}
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"));
}
}
程序最終執(zhí)行結(jié)果是：
對(duì)于兩個(gè)文件的比對(duì)個(gè)人認(rèn)為可以參照這種算法思想（自己現(xiàn)在并為實(shí)現(xiàn)），在日后的博客中將會(huì)寫到。
上述實(shí)現(xiàn)過程中，用數(shù)組保存了所有的公共子串信息，然后排序取最大的子串，這種做法如果只是求最大子串的話，算法就不是很合理，因此做了如下修改，List只保存當(dāng)前計(jì)算中最大的子串，具體實(shí)現(xiàn)如下：
/**
*@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長(zhǎng)度做行
b = s2.length();//s2長(zhǎng)度做列
if(a== 0 || b == 0) {
return "";
}
//設(shè)置匹配矩陣
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;
}
}
}
//求所有公因子字符串，保存信息為相對(duì)第二個(gè)字符串的起始位置和長(zhǎng)度
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("\n");
}
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，保存所有子串，下面的判斷，只保存當(dāng)前最大的子串
//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，保存所有子串，下面的判斷，只保存當(dāng)前最大的子串
//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"));
}
}
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
JAVA異常處理機(jī)制之throws/throw使用情況
這篇文章主要介紹了JAVA異常處理機(jī)制之throws/throw使用情況的區(qū)別，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
這篇文章主要介紹了SpringBoot中使用攔截器的配置詳解,攔截器是?AOP?的一種實(shí)現(xiàn),專門攔截對(duì)動(dòng)態(tài)資源的后臺(tái)請(qǐng)求,即攔截對(duì)控制層的請(qǐng)?求,使用場(chǎng)景比較多的是判斷用戶是否有權(quán)限請(qǐng)求后臺(tái),需要的朋友可以參考下2024-01-01
這篇文章主要介紹了SpringBoot Kafka 整合使用及安裝教程，本文圖文并茂給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2019-07-07
這篇文章主要介紹了Mybatis注解方式@Insert的用法說明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要介紹了Spring中單例和多例的深入理解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-08-08
詳解mybatis插入數(shù)據(jù)后返回自增主鍵ID的問題
這篇文章主要介紹了mybatis插入數(shù)據(jù)后返回自增主鍵ID詳解,本文通過場(chǎng)景分析示例代碼相結(jié)合給大家介紹的非常詳細(xì)，需要的朋友可以參考下2021-07-07
這篇文章主要給大家介紹了關(guān)于Java中List集合去重方法以及效率對(duì)比的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
這篇文章主要介紹了JAVA文件掃描（遞歸）的實(shí)例代碼 ,代碼簡(jiǎn)單易懂，非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2019-06-06 
這篇文章主要介紹了Spring框架中的@Conditional系列注解詳解,我們需要一個(gè)類實(shí)現(xiàn)Spring提供的Condition接口,它會(huì)匹配@Conditional所符合的方法,然后我們可以使用我們?cè)贎Conditional注解中定義的類來檢查,需要的朋友可以參考下
2024-01-01