Consecutive words match in a dataset I have written an algorithm to do consecutive word match in a dataset

The input is a dataset (list of textlines) and I want to scan that and return repeated word(s) in the dataset along with some metadata like the strings (lines) they matched at. 

I am having hard time to wrap my mind around a better approach to hand the consecutive words match. What I have so far is:


hashtable datastructure  
I compute the permutations of each sentence's words. So complexity is n+ (n*avg words count). e.g: abc def gg ww will produce the following permutations

-- abc def
-- abc def gg
-- abc def gg ww
-- def gg
-- def gg ww
-- gg ww  
I store every possible word combination from each sentence in a dictionary with value of 1 
if a word combination exists in the dictionary, I increase the value by 1
using stringBuilder to avoid string immutability
I refine my dictionary at the end to remove any items that has value of 1 


I am curios if:
1) this can be improved
2) are there any other datastructures/algo I can use to do the consecutive word matching on a text blob

It is C# now, but we are considering python or Go as well.

public Dictionary&lt;string, List&lt;string&gt;&gt; ConsecutiveMatches { get; set; }

public void Load(List&lt;string&gt; dataset)
{
    for (int i = 0; i &lt; dataset.Count; i++)
    {
        var sentence = dataset[i];
        var words = sentence.Split(" ", StringSplitOptions.RemoveEmptyEntries);

        BuildConsecutiveMatches(words, sentence);
    }

    RefineConsecutiveMatches();
}

private void BuildConsecutiveMatches(string[] words, string sentence)
{
    BuildConsecutiveMatchesRecursive(words, 0, sentence);
}

private void BuildConsecutiveMatchesRecursive(string[] words, int index, string sentence)
{
    if (index &gt;= words.Length - 1)
    {
        return;
    }

    var builder = new StringBuilder(words[index]);
    builder.Append(' ');

    for (int i = index + 1; i &lt; words.Length; i++)
    {
        builder.Append(words[i]);
        var permutation = builder.ToString();
        if (ConsecutiveMatches.TryGetValue(permutation, out var matches))
        {
            ConsecutiveMatches[permutation].Add(sentence);
        }
        else
        {
            ConsecutiveMatches.Add(permutation, new List&lt;string&gt; { sentence });
        }
        builder.Append(' ');
    }

    BuildConsecutiveMatchesRecursive(words, ++index, sentence);
}

private void RefineConsecutiveMatches()
{
    ConsecutiveMatches = ConsecutiveMatches.Where(pair =&gt; pair.Value.Count &gt;= 2)
                            .ToDictionary(pair =&gt; pair.Key,
                                        pair =&gt; pair.Value);
}
The data structure you want is called a trie.  It's often used with letters in the nodes, for doing word search (finding anagrams and so on); in your case the keys would be words and the values would be sub-tries and arrays of line numbers or other metadata.

Given this input:

cat dog pig
dog pig cow


You'd make a structure like:

{
    cat: {
      dog: {
        pig: { "#": [ 1 ] },
        "#": [ 1 ]
      },
      "#": [ 1 ]
    },
    dog: {
      pig: { 
        cow: { "#": [ 2 ] },
        "#": [ 1, 2 ]
      },
      "#": [ 1, 2 ]
    },
    pig: { 
      cow: { "#": [ 2 ] },
      "#": [ 1, 2 ]
    },
    cow: { "#": [ 2 ] },
}