java实现字符串匹配求两个字符串的最大公共子串_java字符串最大匹配 - CSDN文库

字符串匹配算法

公共字符串长度

最大公共子串

147 浏览量更新于2023-03-03 评论收藏 102KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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. 对所有公共因子排序，返回最大的公共因子的值。

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

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);

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

评论0

weixin_38695452

粉丝: 3
资源: 899

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈