java實現字符串匹配求兩個字符串的最大公共子串

更新時間：2016年10月25日 10:16:48 作者：xiaojimanman

這篇文章主要介紹了java實現求兩個字符串最大公共子串的方法，詳細的描述了兩個字符串的最大公共子串算法的實現,需要的朋友可以參考下

本文實例講述了java實現求兩個字符串最大公共子串的方法。分享給大家供大家參考，具體如下：

最近在項目工作中有一個關于文本對比的需求，經過這段時間的學習，總結了這篇博客內容：求兩個字符串的最大公共子串。

算法思想：基于圖計算兩字符串的公共子串。具體算法思想參照下圖：

輸入字符串S1：achmacmh 輸入字符串S2：macham

第a步，是將字符串s1,s2分別按字節(jié)拆分，構成一個二維數組；
二維數組中的值如b所示，比如第一行第一列的值表示字符串s2和s1的第一個字節(jié)是否相等，若相等就是1，否則就是0，最終產生b所示的二維數組；
分別求二維數組中斜線上的公共因子（斜線為元素a右下角值，即a[i][j]的下一個元素是a[i+1][j+1]；公共因子為1所在的位置構成的字符串）；
對所有公共因子排序，返回最大的公共因子的值。

具體的實現代碼如下所示：

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("\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í)行結果是：

對于兩個文件的比對個人認為可以參照這種算法思想（自己現在并為實現），在日后的博客中將會寫到。

上述實現過程中，用數組保存了所有的公共子串信息，然后排序取最大的子串，這種做法如果只是求最大子串的話，算法就不是很合理，因此做了如下修改，List只保存當前計算中最大的子串，具體實現如下：

/**  
 *@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("\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，保存所有子串，下面的判斷，只保存當前最大的子串 
        //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")); 
  } 
}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章: