最长公共子串

Question

我编写了一个程序来查找几个字符串中最长的公共子序列。我使用了一个简单的算法和实现。

其动机是解决http://rosalind.info/problems/lcs/的Rosalind问题。您也可以在那里找到示例输入。Rosalind问题将字符串与DNA联系在一起，但我认为我的代码可以作为一个通用字符串操作来处理。

如果有多个子字符串，这个问题会要求提供任何常见的子字符串，但是我找到了所有的子字符串。

字符串集合的公共子串是集合中每个成员的子串。如果集合的较长的公共子字符串不存在，则公共子字符串是最长公共子串。例如，CG是ACGTACGT和AACCGGTATA的公共子字符串，而GTA是最长的公共子字符串。请注意，可能存在多个最长的公共子字符串。给定:一个DNA串集合(每个长度最多为1 kbp；)。返回:集合中最长的公共子字符串。(如果存在多个解决方案，则可以返回任何单一解决方案。)样本数据集GATTACA ATACA样本输出AC

如何改进这些代码？有什么明显的问题吗？

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace Finding_a_Shared_Motif
{
    class Program
    {
        private static void Main()
        {
            var input = File.ReadAllLines("rosalind_lcs.txt").ToList();

            var t = new Stopwatch();
            t.Restart();
            var lcs = LongestCommonSubstring(input);
            t.Stop();

            File.WriteAllLines("output.txt", lcs);
            Console.WriteLine("Finished in {0} msec.", t.ElapsedMilliseconds);
            Console.ReadLine();
        }

        public static IEnumerable<string> LongestCommonSubstring(List<string> strings)
        {
            var lcs = LongestCommonSubstring(strings[0], strings[1]);

            for (var i = 2; i < strings.Count(); i++)
            {
                var new_lcs = new BestStrings();

                foreach (var s in lcs) new_lcs.Add(LongestCommonSubstring(s, strings[i]));

                lcs = new_lcs;
            }

            return lcs;
        }

        private static BestStrings LongestCommonSubstring(string s1, string s2)
        {
            var lcs = new BestStrings();

            for (var i = 1 - s2.Length; i < s1.Length; i++)
            {
                var substrings = BestSubstringWithAlignment(s1, s2, i);

                if (substrings.Length == 0) continue;

                lcs.Add(substrings);
            }

            return lcs;
        }

        private static BestStrings BestSubstringWithAlignment(string s1, string s2, int offset)
        {
            var substrings = new BestStrings();

            var substring = "";
            for (var i = Math.Max(0, offset); i < s1.Length && i < s2.Length + offset; i++)
            {
                var c1 = s1[i];

                var c2 = s2[i - offset];

                if (c1 == c2)
                {
                    substring = substring + c1;
                }
                else
                {
                    substrings.Add(substring);
                    substring = "";
                }
            }
            substrings.Add(substring);

            return substrings;
        }

        sealed class BestStrings : Collection<string>
        {
            public int Length
            {
                get { return base[0].Length; }
            }

            public BestStrings()
            {
                base.Add("");
            }

            public new void Add(string s)
            {
                if (s.Length == 0 || s.Length < Length || Contains(s)) return;

                if (s.Length > Length) Clear();
                base.Add(s);
            }

            public void Add(IEnumerable<string> collection)
            {
                foreach (var s in collection) Add(s);
            }
        }
    }
}

Answer 1

首先是一些风格。

简单命名的变量根本无助于可读性。c1，c2，s1，s2是个坏主意。我知道这只是一个挑战，而不是生产代码，但保持一致的风格是一个好习惯。

其次，我首先使用string.Contains()方法。它将发现是否存在指定的子字符串，并且应该有助于清理一些代码。

在这个思路中，我决定从第一个字符串中所有可能的子字符串开始，然后搜索所有字符串的列表。

public static IEnumerable<string> LongestCommonSubstrings(List<string> strings)
{
    var firstString = strings.FirstOrDefault();

    var allSubstrings = new List<string>();
    for(int substringLength = firstString.Length -1; substringLength >0; substringLength--)
    {
        for(int offset = 0; (substringLength + offset) < firstString.Length; offset++)
        {
            string currentSubstring = firstString.Substring(offset,substringLength);
            if (!System.String.IsNullOrWhiteSpace(currentSubstring) && !allSubstrings.Contains(currentSubstring))
            {
                allSubstrings.Add(currentSubstring);
            }
        }
    }

    return allSubstrings.OrderBy(subStr => subStr).ThenByDescending(subStr => subStr.Length).Where(subStr => strings.All(currentString => currentString.Contains(subStr)));
}

这还将允许我们在linq上执行一个.FirstOrDefault()，并获得最大的(由于orderby()调用)。

(为了测试，我使用了一个静态字符串列表，而不是一个文件：)

public static void Run()
{
    var input = new List<string>{
        "GATTACA",
        "TAGACCA",
        "ATACA",
    };

    var t = new Stopwatch();
    t.Restart();
    var lcs = LongestCommonSubstrings(input);
    t.Stop();

    Console.WriteLine("All Common substrings: \r\n{0}", string.Join("\r\n", lcs));
    Console.WriteLine("Finished in {0} msec.", t.ElapsedMilliseconds);
    Console.ReadLine();
}

免责声明:尚未完全测试上述代码。可能会伤害你的大脑/电脑。

Answer 2

我不确定你是否对更好的算法感兴趣，但如果是的话，这里有一些。

在这个特定的实现中，我将考虑更改处理子字符串的方式。您目前正在执行大量的字符串连接，每次分配一个新的string对象时，这会很慢。因为您只是在跟踪子字符串，所以可以存储每个匹配的源字符串、启动索引和长度。这将为您节省大量内存，并且运行得更快。

如果您真正依赖于拥有单独的字符串对象，那么至少要知道匹配的范围，然后执行一个substring()来提取它，而不是一次只构建一个字符。