（求LCS和Levenshtein算法改良）文本相似距离检测

//部分匹配的代码，这是遍历了整个字符串了，看到这段代码想死的心都有
public static ​boolean getIsOrNotPartSiilar(string str,String target,float similarDegree){
    ​int limit_distance_length = (int)((1-similarDegree)*Math.min(str.length(),target.length()));
    if(str.length > (target.length()+limit_distance_length))
    ​    ​  return false;
    for(int i=0;i <=target.length()-str.length();i++){
        ​ for(int j=str.length()-limit_distance_length;j<=(str.length()+limit_distance_length);j++){
    ​    ​    ​int endIndex = ((i+j)>= target.length())?(target.length):(i+j);
    ​    ​    ​if(getBooleanByLimitSimilarDegree(str,target.subString(i,endIndex),similarDegree))
    ​    ​    ​    ​return true
    ​    ​}​
    ​}
  return false;
}

//比较两个字符串是否符合给定的Levenshtein距离
public static boolean getBooleanByLimitSimilarDegree(String str,String target,float similarDegree){
    float error_max_limit = (1-similarDegree)*Math.max(str.length(),target.length());
    if((Math.abs(str.length)-target.length()) > error_max_limit)
        return false;
    int[] targetFlag = arrayInit(target);
    int[] moveFlag = new int[target.length()+1];
    for(int i = 0;i < str.length;i++){
        int cost = (str.charAt(i)==target.charAt(j)) ? 0 : 1;
        moveFlag[j+1] = min(targetFlag[j+1]+1,moveFlag[j]+1,targetFlag[j]+cost);
        if((i==j) && (str.charAt(i)!=target.charAt(j))){
            return false;
        }   
     copy(targetFlag,moveFlag);
    }
    return !(moveFlag[target.length() >= error_max_limit]);
}

具体思想看代码吧！！！！！！

[ 本帖最后由 hpp2013 于 2013-11-25 10:36 编辑 ]

这样的字符串应该不唯一，可以有多个相似的，都找出来有点麻烦。
楼主可以试试先找出最长公共子序列，在求公共序列的时候可以将每个字符在B中的位置放在一个位置数组里，然后在得出的位置数组里算哪两点间的距离接近A的长度且包含的点最多，得到就是一个最短的最相似字符串，然后其他的可以再这个字符串的基础上得到。

[ 本帖最后由 zhaogay 于 2013-11-24 11:05 编辑 ]

确实没想那么多，后来想了下，好像是挺麻烦的，表示无能为力啊