春风博客

春天里,百花香...

导航

<2008年6月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

统计

公告

MAIL: junglesong@gmail.com
MSN: junglesong_5@hotmail.com

Locations of visitors to this page

常用链接

留言簿(11)

随笔分类(224)

随笔档案(126)

个人软件下载

我的其它博客

我的邻居们

最新随笔

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

求两字符串的公共子串

求两字符串的公共子串,如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也必然比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_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,

posted on 2008-06-12 17:10 sitinspring 阅读(2208) 评论(0)  编辑  收藏 所属分类: Java基础算法数据结构


只有注册用户登录后才能发表评论。


网站导航:
 
sitinspring(http://www.blogjava.net)原创,转载请注明出处.