求两字符串的公共子串

求两字符串的公共子串，如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（[e-mail]）
 * @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,