求两个字符串的子串(基础算法练习)
?
?
问题描述:
求两字符串中的最大公共子字符串 并输出长度。 例如"abbcgre","abcgra"中最大子字符串"bcgr"
?
?
下面是我的实现:
? 先找出相对较小的一个字符串，从最大长度比较起，逐渐缩小
?比如, abbcgre,abcgra两个字符串,相对长度较小的是abcgra,先看abcgra是否是abbcare的子串,
?如果不是,则长度缩小一位
两种可能 abcgr, bcgra渐次比较,
length=6 索引:0-6?子串:abcgra
?length=5? 0-5,1-6? 子串:abcgr,bcgra
length=?4 索引:?0-4,1-5,2-6 子串:abcg,bcgr,cgra ,cgra,bcgr,abcg
length=3 索引:?0-3,1-4,2-5,3-6?子串:??abc,bcg,cgr,gra gra,cgr,bcg,abc?
?length=2 索引:0-2,1-3,2-4,3-5,4-6 子串:ab,bc,cg,gr,ra
length=1?? 索引:?0-1,1-2,3-4,4-5,5-6 子串:?a,b,c,g,r,a
?
代码:
?
public static String getCommonSub(String str1, String str2) {String bigStr = null;String smallStr = null;if (str1.length() - str2.length() > 0) {bigStr = str1;smallStr = str2;} else {bigStr = str2;smallStr = str1;}for (int i = smallStr.length(); i > 0; i--) {int begain = 0;int end = i;for (int j = smallStr.length() - i; j >= 0; j--) {String result = smallStr.substring(begain, end);if (bigStr.contains(result)) {return result;}begain++;end++;}}return null;}?
?