Longest common substring I wrote a program to find the longest common subsequence among several strings. I used a naive algorithm and implementation.

The motivation was solving the Rosalind problem at http://rosalind.info/problems/lcs/ . You can find sample input there as well. The Rosalind problem concerns strings as DNA, but I think my code can be treated as a general string operation.

The problem asks for any of the common substrings if there is more than one, but I find all of them.

How can this code be improved? What obvious problems are there?

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&lt;string&gt; LongestCommonSubstring(List&lt;string&gt; strings)
        {
            var lcs = LongestCommonSubstring(strings[0], strings[1]);

            for (var i = 2; i &lt; 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 &lt; 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 &lt; s1.Length &amp;&amp; i &lt; 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&lt;string&gt;
        {
            public int Length
            {
                get { return base[0].Length; }
            }

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

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

                if (s.Length &gt; Length) Clear();
                base.Add(s);
            }

            public void Add(IEnumerable&lt;string&gt; collection)
            {
                foreach (var s in collection) Add(s);
            }
        }
    }
}
Firstly some style.

Short named variables don't help readability at all. c1, c2, s1, s2 are a bad idea. I know this is just a challenge and not production code but keeping a consistent style is a good habit.

Secondly I would start by using the string.Contains() method. It will find if a specified substring exists and should help clean up some of the code.

In this train of thought I decided to start with all the possible substrings in the first string and then search the list of all strings.

public static IEnumerable&lt;string&gt; LongestCommonSubstrings(List&lt;string&gt; strings)
{
    var firstString = strings.FirstOrDefault();

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

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


This will also allow us to do a .FirstOrDefault() on the linq and get the largest ( due to the orderby() calls.

(To test I used a static list of strings instead of a file:)

public static void Run()
{
    var input = new List&lt;string&gt;{
        "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();
}


DISCLAIMER: Haven't fully tested the above code. May harm your brain/computer.