Finding longest phrase algorithm

Question

I have this task to find the longest identical phrase which appears in 2 given files. With small files (~500KB each) it works just fine, ~10 secs to finish. But with larger files (~5MB each) it took ~43 mins to complete. The text in larger files are just copied and pasted over and over again. And I want to improve that if possible.

• Book1.txt
• Book2.txt

public static void LongestPhrase(string Book1, string Book2, ref string Phrase, ref int WIndex1, ref int WIndex2)
{
    string[] Words1 = Book1.Split('-');
    string[] Words2 = Book2.Split('-');
    string Fragment = string.Empty;
    int Counter1 = 0, Counter2 = 0;

    Dictionary<string, List<int>> Index1 = new Dictionary<string, List<int>>();
    Dictionary<string, List<int>> Index2 = new Dictionary<string, List<int>>();
    List<string> Repeated = new List<string>();
    List<string> Word1 = new List<string>();
    List<string> Word2 = new List<string>();

    foreach(string Nfo in Words1)
    {
        if (!Word1.Contains(Nfo.ToLower()))
            Word1.Add(Nfo.ToLower());
    }

    foreach (string Nfo in Words2)
    {
        if (!Word2.Contains(Nfo.ToLower()))
            Word2.Add(Nfo.ToLower());
    }

    foreach(string Nfo in Word1)
    {
        if (Word2.Contains(Nfo.ToLower()))
            Repeated.Add(Nfo.ToLower());
    }


    for (int i = 0; i < Words1.Length; i++)
    {
        if (Repeated.Contains(Words1[i].ToLower()))
        {
            if (!Index1.ContainsKey(Words1[i].ToLower()))
            {
                Index1.Add(Words1[i].ToLower(), new List<int>());
                Index1[Words1[i].ToLower()].Add(i);
            }
            else
                Index1[Words1[i].ToLower()].Add(i);
        }
    }

    for (int x = 0; x < Words2.Length; x++)
    {
        if (Repeated.Contains(Words2[x].ToLower()))
        {
            if (!Index2.ContainsKey(Words2[x].ToLower()))
            {
                Index2.Add(Words2[x].ToLower(), new List<int>());
                Index2[Words2[x].ToLower()].Add(x);
            }
            else
                Index2[Words2[x].ToLower()].Add(x);
        }
    }

    foreach (string Nfo in Repeated.OrderByDescending(a => a.Length))
    {

        foreach (int Inf in Index1[Nfo])
        {
            Counter1 = Inf;

            foreach (int Infs in Index2[Nfo])
            {
                Counter2 = Infs;
                int Start1 = 0, Start2 = 0;

                Fragment = Words1[Counter1];

                for (Start1 = Counter1 + 1, Start2 = Counter2 + 1; Start1 < Words1.Length && Start2 < Words2.Length; Start1++, Start2++)
                {
                    if (Words1[Start1].ToLower() == Words2[Start2].ToLower())
                        Fragment += " " + Words1[Start1];
                    else
                        break;
                }

                if (Fragment.Length > Phrase.Length)
                {
                    Phrase = Fragment;
                    WIndex1 = Counter1;
                    WIndex2 = Counter2;
                }
            }
        }
    }
}

static void Main(string[] args)
{
    var watch = Stopwatch.StartNew();
    Console.WriteLine("A");
    string Book1 = File.ReadAllText("Book1.txt", Encoding.GetEncoding(1257));
    string Book2 = File.ReadAllText("Book2.txt", Encoding.GetEncoding(1257));
    string UnfilteredBook1 = Regex.Replace(Book1, @"\s+", "-", RegexOptions.Singleline);
    string UnfilteredBook2 = Regex.Replace(Book2, @"\s+", "-", RegexOptions.Singleline);
    string Phrase = string.Empty; 
    int WordIndex1 = 0, WordIndex2 = 0;
    LongestPhrase(UnfilteredBook1, UnfilteredBook2, ref Phrase, ref WordIndex1, ref WordIndex2);

    watch.Stop();
    var elapsedMs = watch.ElapsedMilliseconds;
    Console.WriteLine("-> {0}", elapsedMs);
}

What I do in my function is this:

1. Make 2 lists from both books containing all different words
2. Make a list of words which are in both books
3. Find all positions of repeated words
4. Go through all repeated words through all found positions and search for phrase

I think 1-3 steps are all right and that 4th could be improved. I just don't have any ideas how. Should I change the approach to find longest phrase?

Answer 1

The first thing that leaped to my eye as that you're using List<string> for huge strings and calling Contains on them. This is very bad for performance, because List<>'s search is an O(n) operation - to check if an item exists, it has to go linearly through the entire collection until it's found.

The data structure you want to be using is HashSet<string>, where checking for the existence of a given string is an O(1) operation, on average. It makes all set operations faster. Note that it can accept a StringComparer object to make it case insensitive, which saves you having to call ToLower on every words, which also slows you down - each ToLower call creates a new String object in memory, which, for large books, will cause a lot of memory pressure.

So the first part of your method can be expressed this way:

string[] Words1 = Book1.Split('-');
string[] Words2 = Book2.Split('-');

// load Book1
HashSet<string> uniqueRepeatedWords 
  = new HashSet<string>(Words1, StringComparer.CurrentCultureIgnoreCase); 

// keep only those in Book2 too.
uniqueRepeatedWords.IntersectWith(Words2); 

Now the Find Positions loops, which can be made more memory-efficient, and mostly remove duplicate code to make things clearer:

// Notice I use a case-insensitive comparer instead of constant ToLower,
// and save the current word once to a local var instead of the 
// noisier and less clear array access every time.
// Additionally, instead of having the same line in both if and else,
// I just create the new List<int> if it doesn't exist, and 
// go back to the same incrementing code after.
var positionsInBook1 = 
   new Dictionary<string, List<int>>(StringComparer.CurrentCultureIgnoreCase);
for (int i = 0; i < Words1.Length; i++)
{
    var word = Words1[i];
    if (uniqueRepeatedWords.Contains(word))
    {
        if (!positionsInBook1 .ContainsKey(word))
        {
            positionsInBook1.Add(word, new List<int>());
        }
        positionsInBook1[word].Add(i);
    }
}

// Now do the same find-position code for Book2 - ideally, move
// the code to different method and call it twice, with different      
// parameters.    
var positionsInBook2 = FindWordPositions(Words2, uniqueRepeatedWords);

General notes

• Your variable naming conventions are confusing. It's customary to name local variables in lowercase (words1, not Words1), and it's very confusing to have variables called Words1 and Word1, both of which being lists of words. I would name them more explicitly - allWordsInBook1, for instance. Similarly, Inf and Infs are almost identical and very confusion. posInBook1 and posInBook2 might be clearer.

• I'd suggest not defining your variables at the top of the method, but closer to where you use them. In your code, when you start using Index1, for instance, you have to scroll back a page to remember what it is.

• You're not actually incrementing Counter1 and Counter3 anywhere, are you? They're always identical to Inf and Infs respectively? In that case, they're just adding visual noise and cognitive weight. Start1/Start2 should be named counter1/counter2, since they're the ones that are incremented.

• Again, every time you find yourself check for equality with ToLower, replace it with string1.Equals(string2, StringComparison.CurrentCultureIgnoreCase). When dealing with a huge number of strings inside nested loops, this can have a real effect on memory usage.

• In your Main method, you're reading a file, using Regex to replace whitespace with a hyphen, then splitting on the hyphen inside the method. Why not save a stage (and a copy of the whole string) by splitting on the regex directly? Regex.Split can do it easily:

  var wordsInBook1 = Regex.Split(Book1, @"\s+|-");

Answer 2

The only approach I can suggest is to use an LCP array.

Since my first implementation has extremely slow sorting of suffic array, I decided to base my new solution on the Sais implementation of the induced sorting based suffix array construction algorithm. It has a complexity of \$O(n)\$.

Here is my new implementation.

---

Simplified Sais algorithm implementation

Creates sorted int[] suffix array.
It has unreadable code, but it is very fast.

internal interface IBaseArray
{
    int this[int i] { get; set; }
}


internal sealed class IntArray : IBaseArray
{
    private readonly int[] m_array;
    private readonly int m_pos;

    public IntArray(int[] array, int pos)
    {
        m_pos = pos;
        m_array = array;
    }

    public int this[int i]
    {
        get { return m_array[i + m_pos]; }
        set { m_array[i + m_pos] = value; }
    }
}

/// <summary>
/// An implementation of the induced sorting based suffix array construction algorithm.
/// </summary>
public static class Sais
{
    private const int MINBUCKETSIZE = 256;

    private static void getCounts(IBaseArray t, IBaseArray c, int n, int k)
    {
        int i;
        for (i = 0; i < k; ++i)
        {
            c[i] = 0;
        }
        for (i = 0; i < n; ++i)
        {
            c[t[i]] = c[t[i]] + 1;
        }
    }

    private static void getBuckets(IBaseArray c, IBaseArray b, int k, bool end)
    {
        int i, sum = 0;
        if (end)
        {
            for (i = 0; i < k; ++i)
            {
                sum += c[i];
                b[i] = sum;
            }
        }
        else
        {
            for (i = 0; i < k; ++i)
            {
                sum += c[i];
                b[i] = sum - c[i];
            }
        }
    }

    /* sort all type LMS suffixes */

    private static void LMSsort(IBaseArray t, int[] sa, IBaseArray c, IBaseArray B, int n, int k)
    {
        int i;
        int c0, c1;
        /* compute SAl */
        if (c == B)
        {
            getCounts(t, c, n, k);
        }
        getBuckets(c, B, k, false); /* find starts of buckets */
        int j = n - 1;
        int b = B[c1 = t[j]];
        --j;
        sa[b++] = (t[j] < c1) ? ~j : j;
        for (i = 0; i < n; ++i)
        {
            if (0 < (j = sa[i]))
            {
                if ((c0 = t[j]) != c1)
                {
                    B[c1] = b;
                    b = B[c1 = c0];
                }
                --j;
                sa[b++] = (t[j] < c1) ? ~j : j;
                sa[i] = 0;
            }
            else if (j < 0)
            {
                sa[i] = ~j;
            }
        }
        /* compute SAs */
        if (c == B)
        {
            getCounts(t, c, n, k);
        }
        getBuckets(c, B, k, true); /* find ends of buckets */
        for (i = n - 1, b = B[c1 = 0]; 0 <= i; --i)
        {
            if (0 < (j = sa[i]))
            {
                if ((c0 = t[j]) != c1)
                {
                    B[c1] = b;
                    b = B[c1 = c0];
                }
                --j;
                sa[--b] = (t[j] > c1) ? ~(j + 1) : j;
                sa[i] = 0;
            }
        }
    }

    private static int LMSpostproc(IBaseArray t, int[] sa, int n, int m)
    {
        int i, j, p, q;
        int qlen, name;
        int c1;

        /* compact all the sorted substrings into the first m items of SA
            2*m must be not larger than n (proveable) */
        for (i = 0; (p = sa[i]) < 0; ++i)
        {
            sa[i] = ~p;
        }
        if (i < m)
        {
            for (j = i, ++i;; ++i)
            {
                if ((p = sa[i]) < 0)
                {
                    sa[j++] = ~p;
                    sa[i] = 0;
                    if (j == m)
                    {
                        break;
                    }
                }
            }
        }

        /* store the length of all substrings */
        i = n - 1;
        j = n - 1;
        int c0 = t[n - 1];
        do
        {
            c1 = c0;
        } while ((0 <= --i) && ((c0 = t[i]) >= c1));
        for (; 0 <= i;)
        {
            do
            {
                c1 = c0;
            } while ((0 <= --i) && ((c0 = t[i]) <= c1));
            if (0 <= i)
            {
                sa[m + ((i + 1) >> 1)] = j - i;
                j = i + 1;
                do
                {
                    c1 = c0;
                } while ((0 <= --i) && ((c0 = t[i]) >= c1));
            }
        }

        /* find the lexicographic names of all substrings */
        for (i = 0, name = 0, q = n, qlen = 0; i < m; ++i)
        {
            p = sa[i];
            int plen = sa[m + (p >> 1)];
            bool diff = true;
            if ((plen == qlen) && ((q + plen) < n))
            {
                for (j = 0; (j < plen) && (t[p + j] == t[q + j]); ++j)
                {
                }
                if (j == plen)
                {
                    diff = false;
                }
            }
            if (diff)
            {
                ++name;
                q = p;
                qlen = plen;
            }
            sa[m + (p >> 1)] = name;
        }

        return name;
    }

    /* compute SA and BWT */

    private static void induceSA(IBaseArray t, int[] sa, IBaseArray c, IBaseArray B, int n, int k)
    {
        int b, i, j;
        int c0, c1;
        /* compute SAl */
        if (c == B)
        {
            getCounts(t, c, n, k);
        }
        getBuckets(c, B, k, false); /* find starts of buckets */
        j = n - 1;
        b = B[c1 = t[j]];
        sa[b++] = ((0 < j) && (t[j - 1] < c1)) ? ~j : j;
        for (i = 0; i < n; ++i)
        {
            j = sa[i];
            sa[i] = ~j;
            if (0 < j)
            {
                if ((c0 = t[--j]) != c1)
                {
                    B[c1] = b;
                    b = B[c1 = c0];
                }
                sa[b++] = ((0 < j) && (t[j - 1] < c1)) ? ~j : j;
            }
        }
        /* compute SAs */
        if (c == B)
        {
            getCounts(t, c, n, k);
        }
        getBuckets(c, B, k, true); /* find ends of buckets */
        for (i = n - 1, b = B[c1 = 0]; 0 <= i; --i)
        {
            if (0 < (j = sa[i]))
            {
                if ((c0 = t[--j]) != c1)
                {
                    B[c1] = b;
                    b = B[c1 = c0];
                }
                sa[--b] = ((j == 0) || (t[j - 1] > c1)) ? ~j : j;
            }
            else
            {
                sa[i] = ~j;
            }
        }
    }

    private static int computeBWT(IBaseArray t, int[] sa, IBaseArray c, IBaseArray B, int n, int k)
    {
        int b, i, j, pidx = -1;
        int c0, c1;
        /* compute SAl */
        if (c == B)
        {
            getCounts(t, c, n, k);
        }
        getBuckets(c, B, k, false); /* find starts of buckets */
        j = n - 1;
        b = B[c1 = t[j]];
        sa[b++] = ((0 < j) && (t[j - 1] < c1)) ? ~j : j;
        for (i = 0; i < n; ++i)
        {
            if (0 < (j = sa[i]))
            {
                sa[i] = ~(c0 = t[--j]);
                if (c0 != c1)
                {
                    B[c1] = b;
                    b = B[c1 = c0];
                }
                sa[b++] = ((0 < j) && (t[j - 1] < c1)) ? ~j : j;
            }
            else if (j != 0)
            {
                sa[i] = ~j;
            }
        }
        /* compute SAs */
        if (c == B)
        {
            getCounts(t, c, n, k);
        }
        getBuckets(c, B, k, true); /* find ends of buckets */
        for (i = n - 1, b = B[c1 = 0]; 0 <= i; --i)
        {
            if (0 < (j = sa[i]))
            {
                sa[i] = (c0 = t[--j]);
                if (c0 != c1)
                {
                    B[c1] = b;
                    b = B[c1 = c0];
                }
                sa[--b] = ((0 < j) && (t[j - 1] > c1)) ? ~t[j - 1] : j;
            }
            else if (j != 0)
            {
                sa[i] = ~j;
            }
            else
            {
                pidx = i;
            }
        }
        return pidx;
    }

    /* find the suffix array SA of T[0..n-1] in {0..k-1}^n
       use a working space (excluding T and SA) of at most 2n+O(1) for a constant alphabet */

    private static int sais_main(IBaseArray t, int[] sa, int fs, int n, int k, bool isbwt)
    {
        IBaseArray c, B;
        int i;
        int name, pidx = 0;
        int c1;
        uint flags;

        if (k <= MINBUCKETSIZE)
        {
            c = new IntArray(new int[k], 0);
            if (k <= fs)
            {
                B = new IntArray(sa, n + fs - k);
                flags = 1;
            }
            else
            {
                B = new IntArray(new int[k], 0);
                flags = 3;
            }
        }
        else if (k <= fs)
        {
            c = new IntArray(sa, n + fs - k);
            if (k <= (fs - k))
            {
                B = new IntArray(sa, n + fs - k * 2);
                flags = 0;
            }
            else if (k <= (MINBUCKETSIZE * 4))
            {
                B = new IntArray(new int[k], 0);
                flags = 2;
            }
            else
            {
                B = c;
                flags = 8;
            }
        }
        else
        {
            c = B = new IntArray(new int[k], 0);
            flags = 4 | 8;
        }

        /* stage 1: reduce the problem by at least 1/2
           sort all the LMS-substrings */
        getCounts(t, c, n, k);
        getBuckets(c, B, k, true); /* find ends of buckets */
        for (i = 0; i < n; ++i)
        {
            sa[i] = 0;
        }
        int b = -1;
        i = n - 1;
        int j = n;
        int m = 0;
        int c0 = t[n - 1];
        do
        {
            c1 = c0;
        } while ((0 <= --i) && ((c0 = t[i]) >= c1));
        for (; 0 <= i;)
        {
            do
            {
                c1 = c0;
            } while ((0 <= --i) && ((c0 = t[i]) <= c1));
            if (0 <= i)
            {
                if (0 <= b)
                {
                    sa[b] = j;
                }
                b = --B[c1];
                j = i;
                ++m;
                do
                {
                    c1 = c0;
                } while ((0 <= --i) && ((c0 = t[i]) >= c1));
            }
        }
        if (1 < m)
        {
            LMSsort(t, sa, c, B, n, k);
            name = LMSpostproc(t, sa, n, m);
        }
        else if (m == 1)
        {
            sa[b] = j + 1;
            name = 1;
        }
        else
        {
            name = 0;
        }

        /* stage 2: solve the reduced problem
           recurse if names are not yet unique */
        if (name < m)
        {
            if ((flags & 4) != 0)
            {
                c = null;
                B = null;
            }
            if ((flags & 2) != 0)
            {
                B = null;
            }
            int newfs = (n + fs) - (m * 2);
            if ((flags & (1 | 4 | 8)) == 0)
            {
                if ((k + name) <= newfs)
                {
                    newfs -= k;
                }
                else
                {
                    flags |= 8;
                }
            }
            for (i = m + (n >> 1) - 1, j = m * 2 + newfs - 1; i >= m; --i)
            {
                if (sa[i] != 0)
                {
                    sa[j--] = sa[i] - 1;
                }
            }
            IBaseArray ra = new IntArray(sa, m + newfs);
            sais_main(ra, sa, newfs, m, name, false);

            i = n - 1;
            j = m * 2 - 1;
            c0 = t[n - 1];
            do
            {
                c1 = c0;
            } while ((0 <= --i) && ((c0 = t[i]) >= c1));
            for (; 0 <= i;)
            {
                do
                {
                    c1 = c0;
                } while ((0 <= --i) && ((c0 = t[i]) <= c1));
                if (0 <= i)
                {
                    sa[j--] = i + 1;
                    do
                    {
                        c1 = c0;
                    } while ((0 <= --i) && ((c0 = t[i]) >= c1));
                }
            }

            for (i = 0; i < m; ++i)
            {
                sa[i] = sa[m + sa[i]];
            }
            if ((flags & 4) != 0)
            {
                c = B = new IntArray(new int[k], 0);
            }
            if ((flags & 2) != 0)
            {
                B = new IntArray(new int[k], 0);
            }
        }

        /* stage 3: induce the result for the original problem */
        if ((flags & 8) != 0)
        {
            getCounts(t, c, n, k);
        }
        /* put all left-most S characters into their buckets */
        if (1 < m)
        {
            getBuckets(c, B, k, true); /* find ends of buckets */
            i = m - 1;
            j = n;
            int p = sa[m - 1];
            c1 = t[p];
            do
            {
                int q = B[c0 = c1];
                while (j > q)
                {
                    sa[--j] = 0;
                }
                do
                {
                    sa[--j] = p;
                    if (--i < 0)
                    {
                        break;
                    }
                    p = sa[i];
                } while ((c1 = t[p]) == c0);
            } while (0 <= i);

            while (0 < j)
            {
                sa[--j] = 0;
            }
        }
        if (isbwt == false)
        {
            induceSA(t, sa, c, B, n, k);
        }
        else
        {
            pidx = computeBWT(t, sa, c, B, n, k);
        }
        return pidx;
    }


    /// <summary>
    /// Constructs the suffix array of a given sequence in linear time.
    /// </summary>
    /// <param name="t">input sequence</param>
    /// <param name="k">alphabet size</param>
    /// <returns>output suffix array</returns>
    public static int[] sufsort(int[] t, int k)
    {
        if (t == null)
            throw new ArgumentNullException("t");

        if (k <= 0)
            throw new ArgumentOutOfRangeException("k");

        // Length of the given string
        int n = t.Length;

        // Output suffix array
        int[] sa = new int[n];

        return n <= 1 || sais_main(new IntArray(t, 0), sa, 0, n, k, false) == 0 ? sa : null;
    }
}

---

LongestCommonPhraseInfo class

A class that will hold a result

public sealed class LongestCommonPhraseInfo
{
    public readonly string[] CommonPhraseWords;
    public readonly int WordIndex1;
    public readonly int WordIndex2;

    public LongestCommonPhraseInfo(string[] commonPhraseWords, int wordIndex1, int wordIndex2)
    {
        CommonPhraseWords = commonPhraseWords;
        WordIndex1 = wordIndex1;
        WordIndex2 = wordIndex2;
    }

    public string Phrase
    {
        get { return String.Join(" ", CommonPhraseWords); }
    }
}

---

The main class

Calls the Sais algorithm class to create a suffix array and creates the corresponding LCP array. It contains a public method GetLongestCommonPhrase and a tiny utility method Between<T>:

/// <summary>
/// Checks if <paramref name="x"/> value is between values 
/// <paramref name="a"/> and <paramref name="b"/> (or 
/// <paramref name="b"/> and <paramref name="a"/>).
/// </summary>
/// <typeparam name="T">Type of arguments.</typeparam>
private static bool Between<T>(T x, T a, T b)
    where T : IComparable<T>
{
    return a.CompareTo(b) <= 0
               ? x.CompareTo(a) >= 0 && x.CompareTo(b) <= 0
               : x.CompareTo(a) <= 0 && x.CompareTo(b) >= 0;
}

public static LongestCommonPhraseInfo GetLongestCommonPhrase(string text1, string text2)
{
    const string Sentinel1 = "\x00";
    const string Sentinel2 = "\x01";

    // Split texts.
    string[] textWords1 = Regex.Split(text1, @"\s+|-+", RegexOptions.Compiled | RegexOptions.Singleline);
    string[] textWords2 = Regex.Split(text2, @"\s+|-+", RegexOptions.Compiled | RegexOptions.Singleline);

    // Combine texts into single array.
    string[] textWords = new string[textWords1.Length + textWords2.Length + 2];
    Array.Copy(textWords1, textWords, textWords1.Length);
    textWords[textWords1.Length] = Sentinel1;
    Array.Copy(textWords2, 0, textWords, textWords1.Length + 1, textWords2.Length);
    textWords[textWords.Length - 1] = Sentinel2;

    // Get distinct words of text.
    string[] alphabet = textWords.Distinct().ToArray();

    // Create temp dictionary.
    // Key: alphabet element.
    // Value: index in alphabet.
    Dictionary<string, int> wordsIndex = new Dictionary<string, int>(alphabet.Length);
    for (int i = 0; i < alphabet.Length; i++)
        wordsIndex[alphabet[i]] = i;

    // Convert each word of the text to its index.
    int[] indexedText = Array.ConvertAll(textWords, w => wordsIndex[w]);

    // Call the Sais algorithm to create int[] suffix array.
    int[] sa = Sais.sufsort(indexedText, alphabet.Length);
    if (sa == null)
        return null;

    // If succeededб create LCP array.
    int[] lcps = new int[sa.Length];
    int prev = sa[0];
    int maxLcp = -1;
    int maxLcpIndex = -1;

    for (int i = 1; i < lcps.Length; i++)
    {
        int cur = sa[i];

        if (Between(textWords1.Length, prev, cur))
        {
            // If `prev` and `cur` suffixes belong to different text parts.

            // Calculate the LCP.
            int lcp = 0;
            while (indexedText[prev + lcp] == indexedText[cur + lcp])
            {
                lcp++;
            }
            // Find the maximum LCP.
            if (lcp > maxLcp)
            {
                maxLcp = lcp;
                maxLcpIndex = i;
            }
        }

        prev = cur;
    }

    int[] tmp = new int[maxLcp];
    Array.Copy(indexedText, sa[maxLcpIndex], tmp, 0, maxLcp);

    return new LongestCommonPhraseInfo(Array.ConvertAll(tmp, i => alphabet[i]),
        Math.Min(sa[maxLcpIndex], sa[maxLcpIndex - 1]),
        Math.Max(sa[maxLcpIndex], sa[maxLcpIndex - 1]));
}

Usage sample:

var book1 = File.ReadAllText("50503-0.txt").ToLower();
var book2 = File.ReadAllText("50511-0.txt").ToLower();

    // Read the books.
    string book1 = File.ReadAllText(@"D:\50503-0.txt").ToLower();
    string book2 = File.ReadAllText(@"D:\50511-0.txt").ToLower();

    // Make the books longer.
    // !!! FOR TESTS ONLY !!!
    string text1 = String.Concat(book1, " word1 ", book1, " word2 ", book1, " word3 ", book1);
    string text2 = String.Concat(book2, " word4 ", book2, " word5 ", book2, " word6 ", book2);

    // Go!
    Stopwatch sw = new Stopwatch();
    sw.Start();

    // Find the longest phrase.
    var longestPhrase = GetLongestCommonPhrase(text1, text2);

    sw.Stop();

    if (longestPhrase != null)
    {
        Console.WriteLine("Common Phrase Words Count: {0}", longestPhrase.CommonPhraseWords.Length);
        Console.WriteLine("Common Phrase: \"{0}...\"", longestPhrase.Phrase.Substring(0, 64));
        Console.WriteLine("Time elapsed (ms): {0}", sw.ElapsedMilliseconds);
    }
    else
    {
        Console.WriteLine("Failed!");
    }

Output for enlarged texts (on my PC):

Common Phrase Words Count: 2999
Common Phrase: "updated editions will replace the previous one the old editions ..."
Time elapsed (ms): 4537

For non-enlarged texts:

Time elapsed (ms): 1241