如何用C来寻找最长公共子串++(How to find Longest Common Substri

2019-06-23 19:12发布

站内文章 / 前沿技术
56 0 0

我在网上搜了一个C ++最长公共子串实现，但未能找到一个体面的一个。 我需要返回字符串本身LCS算法，所以它不只是LCS。

我不知道，不过，我如何能做到这一点多个字符串之间。

我的想法是检查2串之间的最长的一个，然后去检查所有的人，但是这是一个非常缓慢的过程，需要对内存管理许多长串，使我的程序相当缓慢。

这是如何任何想法可以加快多个字符串？ 谢谢。

重要的编辑之一，我给出的变量决定串最长公共子需要在数量，所以我可以给10串，并发现他们所有的LCS（K = 10），或4 LCS他们，但我没有告诉其中4，我一定要找到最好的4。

Answer 1:

这里是一个很好的文章发现所有常见的子字符串有效，与C.例子，如果你只需要最长的，这可能是矫枉过正，但它可能会更容易比约后缀树一般的文章来了解。



Answer 2:

答案是广义后缀树。 http://en.wikipedia.org/wiki/Generalised_suffix_tree

你可以建立多个字符串广义后缀树。

看看这个http://en.wikipedia.org/wiki/Longest_common_substring_problem

后缀树可以建在O（n）的时间对于每个字串，K * O（n）的合计。 K是字符串的总数。

所以这是非常快的解决这个问题。



Answer 3:

这是一个动态规划问题，并且可以解决在O（MN）时间，其中m是一个字符串的长度，n是其他。

像任何其他问题，用动态规划解决的，我们将划分问题转化为子问题。 比方说，如果两个字符串X1X2X3 .... XM和y1y2y3 ... YN

S（I，J）是X1X2X3 ... xi和y1y2y3的最长的子串.... YJ，然后

S（I，J）= MAX {最长公共子的长度在XI /结束YJ，如果（X [I] == Y [j]），S（I-1，J-1），S（I，J -1），S（I-1，J）}

这里是用Java工作程序。 我相信你可以将其转换为C ++： 

public class LongestCommonSubstring {

    public static void main(String[] args) {
        String str1 = "abcdefgijkl";
        String str2 = "mnopabgijkw";
        System.out.println(getLongestCommonSubstring(str1,str2));
    }

    public static String getLongestCommonSubstring(String str1, String str2) {
        //Note this longest[][] is a standard auxialry memory space used in Dynamic
                //programming approach to save results of subproblems. 
                //These results are then used to calculate the results for bigger problems
        int[][] longest = new int[str2.length() + 1][str1.length() + 1];
        int min_index = 0, max_index = 0;

                //When one string is of zero length, then longest common substring length is 0
        for(int idx = 0; idx < str1.length() + 1; idx++) {
            longest[0][idx] = 0;
        }

        for(int idx = 0; idx < str2.length() + 1; idx++) {
            longest[idx][0] = 0;
        }

        for(int i = 0; i <  str2.length(); i++) {
            for(int j = 0; j < str1.length(); j++) {

                int tmp_min = j, tmp_max = j, tmp_offset = 0;

                if(str2.charAt(i) == str1.charAt(j)) {
                    //Find length of longest common substring ending at i/j
                    while(tmp_offset <= i && tmp_offset <= j &&
                            str2.charAt(i - tmp_offset) == str1.charAt(j - tmp_offset)) {

                        tmp_min--;
                        tmp_offset++;

                    }
                }
                //tmp_min will at this moment contain either < i,j value or the index that does not match
                //So increment it to the index that matches.
                tmp_min++;

                //Length of longest common substring ending at i/j
                int length = tmp_max - tmp_min + 1;
                //Find the longest between S(i-1,j), S(i-1,j-1), S(i, j-1)
                int tmp_max_length = Math.max(longest[i][j], Math.max(longest[i+1][j], longest[i][j+1]));

                if(length > tmp_max_length) {
                    min_index = tmp_min;
                    max_index = tmp_max;
                    longest[i+1][j+1] = length;
                } else {
                    longest[i+1][j+1] = tmp_max_length;
                }


            }
        }

        return str1.substring(min_index, max_index >= str1.length() - 1 ? str1.length() - 1 : max_index + 1);
    }
}


Answer 4:

有一个非常优雅的动态规划解决这个。

让LCSuff[i][j]是的最长的共同后缀X[1..m]和Y[1..n] 。 我们这里有两种情况：

  • X[i] == Y[j] ，这意味着我们可以扩展之间的最常见的后缀X[i-1]和Y[j-1] 。 因此LCSuff[i][j] = LCSuff[i-1][j-1] + 1在这种情况下。

  • X[i] != Y[j]自上次文字本身是不同的， X[1..i]和Y[1..j]不能有一个共同的后缀。 因此， LCSuff[i][j] = 0在此情况下。

现在，我们需要检查这些最长公共后缀的最大。

所以， LCSubstr(X,Y) = max(LCSuff(i,j))其中1<=i<=m和1<=j<=n

该算法相当多，现在自己写的。 

string LCSubstr(string x, string y){
    int m = x.length(), n=y.length();

    int LCSuff[m][n];

    for(int j=0; j<=n; j++)
        LCSuff[0][j] = 0;
    for(int i=0; i<=m; i++)
        LCSuff[i][0] = 0;

    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(x[i-1] == y[j-1])
                LCSuff[i][j] = LCSuff[i-1][j-1] + 1;
            else
                LCSuff[i][j] = 0;
        }
    }

    string longest = "";
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(LCSuff[i][j] > longest.length())
                longest = x.substr((i-LCSuff[i][j]+1) -1, LCSuff[i][j]);
        }
    }
    return longest;
}


Answer 5:

这里是一个C＃版本使用两个阵列的动态规划寻找最长公共子串（可参考： http://codingworkout.blogspot.com/2014/07/longest-common-substring.html有详细介绍） 

class LCSubstring
        {
            public int Length = 0;
            public List<Tuple<int, int>> indices = new List<Tuple<int, int>>();
        }
        public string[] LongestCommonSubStrings(string A, string B)
        {
            int[][] DP_LCSuffix_Cache = new int[A.Length+1][];
            for (int i = 0; i <= A.Length; i++)
            {
                DP_LCSuffix_Cache[i] = new int[B.Length + 1];
            }
            LCSubstring lcsSubstring = new LCSubstring();
            for (int i = 1; i <= A.Length; i++)
            {
                for (int j = 1; j <= B.Length; j++)
                {
                    //LCSuffix(Xi, Yj) = 0 if X[i] != X[j]
                    //                 = LCSuffix(Xi-1, Yj-1) + 1 if Xi = Yj
                    if (A[i - 1] == B[j - 1])
                    {
                        int lcSuffix = 1 + DP_LCSuffix_Cache[i - 1][j - 1];
                        DP_LCSuffix_Cache[i][j] = lcSuffix;
                        if (lcSuffix > lcsSubstring.Length)
                        {
                            lcsSubstring.Length = lcSuffix;
                            lcsSubstring.indices.Clear();
                            var t = new Tuple<int, int>(i, j);
                            lcsSubstring.indices.Add(t);
                        }
                        else if(lcSuffix == lcsSubstring.Length)
                        {
                            //may be more than one longest common substring
                            lcsSubstring.indices.Add(new Tuple<int, int>(i, j));
                        }
                    }
                    else
                    {
                        DP_LCSuffix_Cache[i][j] = 0;
                    }
                }
            }
            if(lcsSubstring.Length > 0)
            {
                List<string> substrings = new List<string>();
                foreach(Tuple<int, int> indices in lcsSubstring.indices)
                {
                    string s = string.Empty;
                    int i = indices.Item1 - lcsSubstring.Length;
                    int j = indices.Item2 - lcsSubstring.Length;
                    Assert.IsTrue(DP_LCSuffix_Cache[i][j] == 0);
                    for(int l =0; l<lcsSubstring.Length;l++)
                    {
                        s += A[i];
                        Assert.IsTrue(A[i] == B[j]);
                        i++;
                        j++;
                    }
                    Assert.IsTrue(i == indices.Item1);
                    Assert.IsTrue(j == indices.Item2);
                    Assert.IsTrue(DP_LCSuffix_Cache[i][j] == lcsSubstring.Length);
                    substrings.Add(s);
                }
                return substrings.ToArray();
            }
            return new string[0];
        }

当单元测试是： 

[TestMethod]
        public void LCSubstringTests()
        {
            string A = "ABABC", B = "BABCA";
            string[] substrings = this.LongestCommonSubStrings(A, B);
            Assert.IsTrue(substrings.Length == 1);
            Assert.IsTrue(substrings[0] == "BABC");
            A = "ABCXYZ"; B = "XYZABC";
            substrings = this.LongestCommonSubStrings(A, B);
            Assert.IsTrue(substrings.Length == 2);
            Assert.IsTrue(substrings.Any(s => s == "ABC"));
            Assert.IsTrue(substrings.Any(s => s == "XYZ"));
            A = "ABC"; B = "UVWXYZ";
            string substring = "";
            for(int i =1;i<=10;i++)
            {
                A += i;
                B += i;
                substring += i;
                substrings = this.LongestCommonSubStrings(A, B);
                Assert.IsTrue(substrings.Length == 1);
                Assert.IsTrue(substrings[0] == substring);
            }
        }


Answer 6:

我想这几种不同的解决方案，但他们都显得很慢，所以我想出了下面，并没有真正考验不多，但它似乎工作快一点给我。 

#include <iostream>

std::string lcs( std::string a, std::string b )
{
    if( a.empty() || b.empty() ) return {} ;

    std::string current_lcs = "";

    for(int i=0; i< a.length(); i++) {
        size_t fpos = b.find(a[i], 0);
        while(fpos != std::string::npos) {
            std::string tmp_lcs = "";
            tmp_lcs += a[i];
            for (int x = fpos+1; x < b.length(); x++) {
                tmp_lcs+=b[x];
                size_t spos = a.find(tmp_lcs, 0);
                if (spos == std::string::npos) {
                    break;
                } else {
                    if (tmp_lcs.length() > current_lcs.length()) {
                        current_lcs = tmp_lcs;
                    }
                }
            }
            fpos = b.find(a[i], fpos+1);
        }
    }
    return current_lcs;
}

int main(int argc, char** argv)
{
    std::cout << lcs(std::string(argv[1]), std::string(argv[2])) << std::endl;
}


Answer 7:

查找所考虑的所有字符串的最大子。 从N个字符串，就会有N个子。 选择那些最大的N.



文章来源: How to find Longest Common Substring using C++
标签： c++ algorithm lcs
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~