Return to Revisions

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