服务器之家：专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|

服务器之家 - 编程语言 - JAVA教程 - java实现字符串匹配求两个字符串的最大公共子串

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

2020-06-27 12:59xiaojimanman JAVA教程

这篇文章主要介绍了java实现求两个字符串最大公共子串的方法，详细的描述了两个字符串的最大公共子串算法的实现,需要的朋友可以参考下

本文实例讲述了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. 对所有公共因子排序，返回最大的公共因子的值。

具体的实现代码如下所示：

?
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"));
  }
}

程序最终执行结果是：

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

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

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

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

  • 字符串匹配
  • Java
  • 最大公共子串

    • 延伸 · 阅读

    精彩推荐
    最近更新
    编辑推荐
    阅读排行
    热门标签
    501 　 2000 　 1433 　 415 　 内存卡 　 随机抽取 　 选择排序法 　 对象池模式 　 子线程 　 下载器 　 十六进制字符 　 响应 　 静态工厂 　 构造函数 　 swt 　 Overview 　 短信猫 　 作业调度 　 空心菱形 　 htmlparser 　 支票 　 金额大写转换 　 终止循环体 　 AspectJ 　 面向切面编程 　 方法名 　 网址信息 　 动态代理模式 　 线程安全 　 最大公共子串 　
    © 2019-2020 服务器之家 版权所有 www.zzvips.com 关于我们联系我们版权申明网站地图