个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章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实现字符串匹配求两个字符串的最大公共子串的文章就讲到这里了,如果你想了解更多关于java实现字符串匹配求两个字符串的最大公共子串的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

26 4 0
文章推荐： svn 清理失败 (cleanup 失败) 的快速解决方法
文章推荐： 万国觉醒亚历山大大帝怎么获得 万国觉醒亚历山大大帝获取攻略
文章推荐： 万国觉醒联盟资源怎么增加 万国觉醒联盟资源获取方法
文章推荐： Java中Date与String相互转换的方法
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com