java实现字符串匹配求两个字符串的最大公共子串

本文实例讲述了java实现求两个字符串最大公共子串的方法。分享给大家供大家参考，具体如下：

最近在项目工作中有一个关于文本对比的需求，经过这段时间的学习，总结了这篇博客内容：求两个字符串的最大公共子串。

算法思想：基于图计算两字符串的公共子串。具体算法思想参照下图：

输入字符串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("\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")); 
  } 
} 

程序最终执行结果是：

对于两个文件的比对个人认为可以参照这种算法思想（自己现在并为实现），在日后的博客中将会写到。

上述实现过程中，用数组保存了所有的公共子串信息，然后排序取最大的子串，这种做法如果只是求最大子串的话，算法就不是很合理，因此做了如下修改，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")); 
  } 
} 

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！