Finding longest phrase algorithm

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+|-");

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

Let's create 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 that creates a suffix array and the corresponding LCP array. It contains a private nested class Suffix and a public method GetLongestCommonPhrase:

public sealed class SuffixArray
{
    private sealed class Suffix : IComparable<Suffix>
    {
        public static string[] Words { get; internal set; }
        public static int TextMargin { get; internal set; }

        public readonly int StartIndex;

        public Suffix(int startIndex)
        {
            StartIndex = startIndex;
        }

        public int CompareTo(Suffix other)
        {
            if (ReferenceEquals(this, other))
                return 0;

            int i = 0;
            while (true)
            {
                int cmp = String.CompareOrdinal(Words[i + StartIndex], Words[i + other.StartIndex]);
                if (cmp != 0)
                    return cmp;
                i++;
            }
        }

        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 int Lcp(Suffix other)
        {
            if (!Between(TextMargin, StartIndex, other.StartIndex))
                return 0;

            int i = 0;
            while (true)
            {
                int cmp = String.CompareOrdinal(Words[i + StartIndex], Words[i + other.StartIndex]);
                if (cmp != 0)
                    return i;
                i++;
            }
        }
    }

    private const string Sentinel1 = "\x00";
    private const string Sentinel2 = "\x01";
    private readonly Suffix[] Suffixes;
    private readonly string[] Words;
    private readonly int TextMargin;
    private readonly int[] Lcps;
    private readonly int MaxLcp;
    private readonly int MaxLcpIndex;

    public SuffixArray(string[] words1, string[] words2)
    {
        // Concat the words arrays
        Words = new string[words1.Length + words2.Length + 2];
        words1.CopyTo(Words, 0);
        words2.CopyTo(Words, words1.Length + 1);
        Words[words1.Length] = Sentinel1;
        Words[Words.Length - 1] = Sentinel2;

        TextMargin = words1.Length;

        // Set up static properties of `Suffix` class for the current task
        // (Very bad approach)
        Suffix.Words = Words;
        Suffix.TextMargin = TextMargin;

        // Create a suffix array
        Suffixes = new Suffix[Words.Length - 1];
        for (int i = 0; i < Suffixes.Length; i++)
        {
            Suffixes[i] = new Suffix(i);
        }
        Array.Sort(Suffixes);

        // Create an Lcp array and find the maxLcp
        Lcps = new int[Suffixes.Length];
        Lcps[0] = -1;
        int maxLcp = -1;
        int maxLcpIndex = -1;
        for (int i = 1; i < Suffixes.Length; i++)
        {
            int lcp = Suffixes[i].Lcp(Suffixes[i - 1]);
            Lcps[i] = lcp;
            if (lcp > maxLcp)
            {
                maxLcp = lcp;
                maxLcpIndex = i;
            }
        }

        MaxLcp = maxLcp;
        MaxLcpIndex = maxLcpIndex;
    }

    public LongestCommonPhraseInfo GetLongestCommonPhrase()
    {
        // Set up static properties of `Suffix` class for the current task
        // (Very bad approach)
        Suffix.Words = Words;
        Suffix.TextMargin = TextMargin;

        Suffix words1;
        Suffix words2;

        if (Suffixes[MaxLcpIndex].StartIndex < Suffix.TextMargin)
        {
            words1 = Suffixes[MaxLcpIndex];
            words2 = Suffixes[MaxLcpIndex - 1];
        }
        else
        {                                    
            words1 = Suffixes[MaxLcpIndex - 1];
            words2 = Suffixes[MaxLcpIndex];
        }

        string[] tmp = new string[MaxLcp];
        Array.Copy(Suffix.Words, words1.StartIndex, tmp, 0, tmp.Length);

        return new LongestCommonPhraseInfo(tmp, words1.StartIndex, words2.StartIndex);
    }
}

Usage sample:

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

string[] textWords1 = Regex.Split(book1, @"\s+|-+", RegexOptions.Singleline);
string[] textWords2 = Regex.Split(book2, @"\s+|-+", RegexOptions.Singleline);

Stopwatch sw = new Stopwatch();
sw.Start();
var suffixArray = new SuffixArray(textWords1, textWords2);
var longestPhrase = suffixArray.GetLongestCommonPhrase();
sw.Stop();

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);

Output (on my PC):

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