java实现字符串匹配求两个字符串的最大公共子串
程序员文章站
2024-03-12 19:53:32
本文实例讲述了java实现求两个字符串最大公共子串的方法。分享给大家供大家参考,具体如下:
最近在项目工作中有一个关于文本对比的需求,经过这段时间的学习,总结了这篇博...
本文实例讲述了java实现求两个字符串最大公共子串的方法。分享给大家供大家参考,具体如下:
最近在项目工作中有一个关于文本对比的需求,经过这段时间的学习,总结了这篇博客内容:求两个字符串的最大公共子串。
算法思想:基于图计算两字符串的公共子串。具体算法思想参照下图:
输入字符串s1:achmacmh 输入字符串s2:macham
- 第a步,是将字符串s1,s2分别按字节拆分,构成一个二维数组;
- 二维数组中的值如b所示,比如第一行第一列的值表示字符串s2和s1的第一个字节是否相等,若相等就是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")); } }
程序最终执行结果是:
对于两个文件的比对个人认为可以参照这种算法思想(自己现在并为实现),在日后的博客中将会写到。
上述实现过程中,用数组保存了所有的公共子串信息,然后排序取最大的子串,这种做法如果只是求最大子串的话,算法就不是很合理,因此做了如下修改,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")); } }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
下一篇: Docker镜像的使用