求兩字符串的公共子串，如abc123與123456的公共字串為123，基本想法是在長的字符串前面加上長度等于短字符串的空格前綴，然后拿短字符串與新字符串挨個匹配，匹配上的置上匹配字符，否則置上空格，這樣的新串就包含了匹配字串和空格，再劈分放入set即可，重復的元素會被set略過去。
代碼如下：
package com.sitinspring;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/** *//**
* 求兩字符串的公共子串，如abc123與123456的公共字串為123
*
* @author sitinspring（junglesong@gmail.com）
* @since 2008-6-12 下午02:04:06
* @vsersion 1.00 創建 sitinspring 2008-6-12 下午02:04:06
*/
public class CommonChildString
{
private static final char Space = ' ';
Set<String> commonChildStrSet;
public CommonChildString(String str1,String str2){
// 在str1前加上與str2等長的空格，以免漏過前面的共同字串，這樣做讓ｓｔｒ１也必然比ｓｔｒ２長了
str1=getPrefix(str2.length())+str1;
// 用來存放匹配字串，set能自動過濾掉重復的元素
commonChildStrSet=new HashSet<String>();
for(int i=0;i<str1.length();i++){
// 先取字串
String childStr=getSubString(str1,i, str2.length());
// 找字串和str2匹配的部分，匹配不上的位置上空格，如123和1a3匹配完變成1＿１
String commonStr=getCommonString(childStr,str2);
// 把匹配的結果按空格劈分后加入到Set中
commonChildStrSet.addAll(getSplitResult(commonStr));
}
}
/** *//**
* 去掉空格部分，把不是空格的匹配字串取出放入到鏈表中返回
* @param str
* @return
*/
public List<String> getSplitResult(String str){
List<String> ls=new ArrayList<String>();
str=str.trim();
String[] arr=str.split("\\s+");
for(String tmp:arr){
if(tmp.length()>0){
ls.add(tmp);
}
}
return ls;
}
/** *//**
* 返回長度為為n的空格字符串
* @param n
* @return
*/
private String getPrefix(int n){
StringBuffer sb=new StringBuffer();
for(int i=0;i<n;i++){
sb.append(Space);
}
return sb.toString();
}
/** *//**
* 將op1和op2按位比較，相等取哪一位所在的字符，否則留為空格，比較結果返回
*
* @param op1
* @param op2
* @return
*/
public String getCommonString(String op1,String op2){
StringBuffer sb=new StringBuffer();
for(int i=0;i<op1.length();i++){
char c1=op1.charAt(i);
char c2=op2.charAt(i);
sb.append(c1==c2?c1:Space);
}
return sb.toString();
}
/** *//**
* 從str中從startIndex開始截取長度為length的子字符串
* @param str
* @param startIndex
* @param length
* @return
*/
private String getSubString(String str,int startIndex,int length){
String strTmp=str.substring(startIndex);
int n=strTmp.length();
return strTmp.substring(0, length>n?n:length);
}
public Set<String> getCommonChildStrSet() {
return commonChildStrSet;
}
/** *//**
* 測試
* @param args
*/
public static void main(String[] args){
String op1="123abc456";
String op2="abcdef123789655";
CommonChildString commonChildString=new CommonChildString(op1,op2);
// 輸出觀察
System.out.print(op1+"和"+op2+"的匹配字串有：");
for(String tmp:commonChildString.getCommonChildStrSet()){
System.out.print(tmp+",");
}
System.out.print("\n");
}
}
測試結果：
123abc456和abcdef123789655的匹配字串有：5,123,abc,6,