A = abcdefghijk
   B = abaabcdgfghijkda

   求B中与A最相似的子串，最相似的定义：与Levenshtein算法定义的距离一样，由字符串a变为字符串b的最小编辑距离，一次编辑可以为替换、删除、插入一个字符
   该题感觉也可以通过LCS(最长公共子序列)的距离来解，但感觉思路没理清，求各位大神指教
   求个时间复杂度n^2左右的算法，n^3太慢了，受不了

有人在么，等回复啊，大家回复个吧

//部分匹配的代码，这是遍历了整个字符串了，看到这段代码想死的心都有
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 编辑 ]

帮忙来个n^2作用的算法吧，各位大神救救吧，实在想不出了，LCS那个长度想了好久，太多种情况，实在不好理清思路！！！！

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

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

找最长公共子序列，后面的会覆盖掉前面的相同字符
就比如说A：abc B：ababcadbc
B中与A最相似的是abc，但它回溯找出来的最长公共子序列却是adbc中的abc。
还有个缺陷是，找公共子序列是找得最长的，而往往最相似的不一定是最长的
比如A:abcdefghijk  B:adddbcdefghiadf
B中与A最相似的是bcdefghiadf，却不是最长得abcdefghijk

如果将最长公共子序列的所有字符对应的所有位置都保存各自的数组，然后然后，好吧，还没仔细考虑这个能怎么解决.

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

收到的鲜花

• hpp2013 于 2014-01-17 17:42 送鲜花  3朵  

问题已经解决了，谢谢参与