2013年07月25日

最长公共子串


最长公共子串

这是一个很基础的问题,给定两个字符串,查找两个字符串中最长得公共子串,例如给定串S1="abcdefg" S2="bcdeefg",则其中最长得公共子串便是bcde

分析

补充: 今天回过来看这个问题,发现解答的还是存在很多问题,把题目做复杂了。更加简单的解法可以参考这个链接:http://blog.csdn.net/steven30832/article/details/8260189 我又重新按照上面的思路实现了多种解法,具体可以参考我的代码,点这儿

看到这个问题,依然是动态规划求解,当然可能还有其他的思路,例如使用编程珠玑中提到求解字符串中最长重复子串的问题。随便提下后缀数组,可以在O(OlogN)的情况下查找出最长重复子串,若直接将后缀数组使用到这个题目里面来,需要将两个字符串连接起来,然后再转换成最长重复子串的问题,为了避免无法分清两个字符串的边界,则需要添加一个标识符,例如,S1="abcdabcd" S2="abc",对于这两个字符串,使用一个‘#’连接,变成abcdabcd#abc,然后在排序比较之时,确保前后两个地址是属于不同的字符串。

依然使用动态规划来分析此问题,需要递归表达式,边界条件和中间过程。其中F(i,j)表示从后往前比较,字符串S1的前i个字符和字符串S2的前j个字符中最长得公共子串,由三部分确定,

F(i,j) = max{max{F(i-k,j-k),k},F(i-1,j),F(i,j-1)} (0 <= i < strlen(s1), 0 <= j < strlen(s2))

中间过程便是记录不同F(i,j)值,边界条件则是若i或者j为0,则公共子串长度为0了。

代码

根据上面的分析可以很迅速的写出下面的代码。

int findCommonSequence(const char* first, int flen, const char* second, int slen,int **state){
    if(flen <= 0 || slen <= 0)
        return 0;

    int one = 0, two = 0,three = 0;

    if(state[flen][slen] >= 0)
        return state[flen][slen];

    if(first[flen-1] == second[slen-1]){
        int i = flen - 1,j = slen -1; 
        while(i >= 0 && j >= 0 && first[i--] == second[j--]){
            one++;
        }
        int next = findCommonSequence(first,flen-one,second,slen-one,state);
        state[flen-one][slen-one] = next;
        one = max(one,next);
    }

    two = findCommonSequence(first,flen-1,second,slen,state);
    state[flen-1][slen] = two;
    three = findCommonSequence(first,flen,second,slen-1,state);
    state[flen][slen-1] = three;
    state[flen][slen] = max(one,two,three);
    return state[flen][slen];
}

可以使用回溯来确定起点何在

int backtracing(int **state,int flen, int slen){
    if(state == NULL)
        return -1;
    while(flen >= 0){
        if(state[flen][slen] == state[flen-1][slen]){
            flen--;
        }else if(state[flen][slen] == state[flen-1][slen] + 1){
            return flen - state[flen][slen];
        }
    }
}

总结

类似与这样的问题也有很多,除了前面提到的最长重复子串之外,还有一些。 * 两个字符串的编辑距离 * 最长的回文子串 * 字符串匹配KMP算法

其中编辑距离和这个没什么区别,后面两个思路大致相同,都是进行遍历比较,只是在遍历过程中,使用技巧,减少重复得遍历比较,KMP算法,则需要一个next数组,记录比较失败之后,下次可以从哪儿开始接着比较,这样就不要回到起点重新比较,回文子串,则是利用回文串本身的特点对称性,然后将两种不同对称归一化,奇数对称和偶数对称都转换成奇数对称,找到一个回文串之后,由于对称,下次就可以减少其中的比较。

前一篇: 定长线段最多覆盖点的个数 后一篇: Openstack Rabbitmq(四)