如何比较2个字符串数组并找到所有连续匹配并保存索引？

例如，如果我有以下2个数组：

string[] userSelect = new string[] {"the", "quick", "brown", "dog", "jumps", "over"}; string[] original = new string[] {"the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"}; 

我正在尝试将userSelect数组与原始数组进行比较，并根据索引获取所有连续匹配。 userSelect数组将始终由原始数组中的字符串组成。 所以输出如下：

 int[] match0 = new int[] {0, 1, 2}; // indices for "the quick brown" int[] match2 = new int[] {4, 5}; // indices for "jumps over" int[] match1 = new int[] {3}; // index for "dog" 

userSelect数组长度永远不会超过原始数组长度，但它可以更短，并且单词可以按任何顺序排列。 我该怎么做呢？

Answer 1

这就是我想出的

 var matches = (from l in userSelect.Select((s, i) => new { s, i }) join r in original.Select((s, i) => new { s, i }) on ls equals rs group l by ri - li into g from m in g.Select((l, j) => new { li, j = li - j, k = g.Key }) group m by new { mj, mk } into h select h.Select(t => ti).ToArray()) .ToArray(); 

这将输出

 matches[0] // { 0, 1, 2 } the quick brown matches[1] // { 4, 5 } jumps over matches[2] // { 0 } the matches[3] // { 3 } dog 

使用输入{"the", "quick", "brown", "the", "lazy", "dog"}产生：

 matches[0] // { 0, 1, 2 } the quick brown matches[1] // { 0 } the matches[2] // { 3 } the matches[3] // { 3, 4, 5 } the lazy dog 

请注意，对ToArray的调用是可选的。 如果您实际上不需要数组中的结果，则可以将其保留并节省一点处理时间。

要筛选出与其他较大序列完全包含的任何序列，您可以运行此代码（请注意修改后的查询中的orderby ）：

 var matches = (from l in userSelect.Select((s, i) => new { s, i }) join r in original.Select((s, i) => new { s, i }) on ls equals rs group l by ri - li into g from m in g.Select((l, j) => new { li, j = li - j, k = g.Key }) group m by new { mj, mk } into h orderby h.Count() descending select h.Select(t => ti).ToArray()); int take = 0; var filtered = matches.Where(m => !matches.Take(take++) .Any(n => m.All(i => n.Contains(i)))) .ToArray(); 

Answer 2

如果不能重复单词，这将更容易。 。 。

一般的想法是从原始单词列表创建一个Dictionary> 。 这将告诉你在哪些位置使用了哪些单词。 您的样本的字典将是：

 key="the", value={0, 6} key="quick", value={1} key="brown", value={2} ... etc 

现在，当您获得用户的输入时，您将按顺序逐步浏览它，查找字典中的单词以获取位置列表。

所以你查了一个单词，它就在字典里。 您保存从字典返回的位置。 查找下一个单词。 您需要处理三个条件：

1. 这个词不在字典里。 保存以前的连续分组并转到下一个单词，您可能会在其中开始新的分组。
2. 单词在字典中，但没有返回的位置与预期位置匹配（预期位置比最后一个单词的保存位置多一个）。 保存您之前的连续组并转到下一个单词，您可能会在其中开始新组。
3. 单词在字典中，其中一个返回的位置与预期位置匹配。 保存这些职位并转到下一个单词。

我希望你明白这个主意。

Answer 3

这并不是你想要的，但它是一个非常简洁的方法来获得一个包含所有常见字符串的新数组（即取两个数组的交集）。

 var results = array1.Intersect(array2, StringComparer.OrdinalIgnoreCase); 

执行resutls数组后，将包含在array1和array2中发生的每个字符串（忽略大小写）。

如果你想要一点理论，交叉方法是基于你在lambda演算中对集合进行的交集操作。 C＃中的集合实现了所有常见的集合操作，因此值得熟悉它们。 这是wiki文章的链接; http://en.wikipedia.org/wiki/Intersection_(set_theory）

Answer 4

这不是很优雅，但效率很高。 当谈到指数时，Linq使得它通常比简单的循环更复杂，效率更低。

 string[] userSelect = new string[] { "the", "quick", "brown", "dog", "jumps", "over" }; string[] original = new string[] { "the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog" }; var consecutiveGroups = new Dictionary>(); IList> uniques = new List>(); int maxIndex = Math.Min(userSelect.Length, original.Length); if (maxIndex > 0) { int minIndex = 0; int lastMatch = int.MinValue; for (int i = 0; i < maxIndex; i++) { var us = userSelect[i]; var o = original[i]; if (us == o) { if (lastMatch == i - 1) consecutiveGroups[minIndex].Add(us); else { minIndex = i; consecutiveGroups.Add(minIndex, new List() { us }); } lastMatch = i; } else uniques.Add(Tuple.Create(i, us)); } } 

输出连续组的索引+唯一的索引：

 var consecutiveGroupsIndices = consecutiveGroups .OrderByDescending(kv => kv.Value.Count) .Select(kv => Enumerable.Range(kv.Key, kv.Value.Count).ToArray() .ToArray()); foreach(var consIndexGroup in consecutiveGroupsIndices) Console.WriteLine(string.Join(",", consIndexGroup)); Console.WriteLine(string.Join(",", uniques.Select(u => u.Item1))); 

Answer 5

使用LINQ增加乐趣

经过几次尝试，我想出了一个纯粹的LINQ解决方案，理论上可以是一个单行程。 我确实尝试使其高效，但当然function解决方案将导致重复计算，因为您无法保持状态。

我们首先进行一些预处理，以便以后节省重复计算。 是的，我知道我正在做的索引是一个值得怀疑的做法，但如果你小心它的工作，它会很快到达：

 var index = 0; var lookup = original.ToLookup(s => s, s => index++); 

怪物

 var occurrences = userSelect .Where(lookup.Contains) .SelectMany((s, i) => lookup[s] .Select(j => new { User = userSelect.Skip(i), Original = original.Skip(j), Skipped = i }) .Select(t => t.User.Zip(t.Original, (u, v) => Tuple.Create(u, v, t.Skipped)) .TakeWhile(tuple => tuple.Item1 == tuple.Item2) ) .Select(u => new { Word = s, Start = u.Select(v => v.Item3).Min(), Length = u.Count() }) ) .GroupBy(v => v.Start + v.Length) .Select(g => g.OrderBy(u => u.Start).First()) .GroupBy(v => v.Word) .Select(g => g.OrderByDescending(u => u.Length).First()) .Select(w => Enumerable.Range(w.Start, w.Length).ToArray()) .ToList(); 

用它打印

 foreach (var occurrence in occurrences) { Console.WriteLine( "Maximal match starting with '{0}': [{1}]", userSelect[occurrence[0]], string.Join(", ", occurrence) ); } 

给

 Maximal match starting with 'the': [0, 1, 2] Maximal match starting with 'dog': [3] Maximal match starting with 'jumps': [4, 5] 

很明显， 您不希望在生产中使用此代码，到目前为止，另一个（程序）解决方案将更为可取。 然而，除了lookup之外，该解决方案具有纯function的区别。 当然，这也可以在function上写：

 var lookup = original.Select((s, i) => Tuple.Create) .ToLookup(t => t.Item1, t => t.Item2); 

这个怎么运作

预热，它创建了一个类似字典的结构，将original中的每个单词与它出现在同一集合中的索引相关联。 这将在稍后用于从userSelect每个单词创建尽可能多的匹配序列（例如，“the”将导致两个匹配序列，因为它在original出现两次）。

然后：

 .Where(lookup.Contains) 

这很容易，它不考虑userSelect中没有出现在original userSelect中的所有单词。

  // For each place where the word s appears in original... .SelectMany((s, i) => lookup[s] // Define the two subsequences of userSelect and original to work on. // We are trying to find the number of identical elements until first mismatch. .Select(j => new { User = userSelect.Skip(i), Original = original.Skip(j), Skipped = j }) // Use .Zip to find this subsequence .Select(t => t.User.Zip(t.Original, (u, v) => Tuple.Create(u, v, t.Skipped)).TakeWhile(tuple => tuple.Item1 == tuple.Item2)) // Note the index in original where the subsequence started and its length .Select(u => new { Word = s, Start = u.Select(v => v.Item3).Min(), Length = u.Count() }) ) 

此时，我们已将userSelect中的每个匹配单词userSelect到具有“ Start和“ Length属性的匿名对象。 然而，匹配长度为N的序列也将导致较小的长度为N-1，N-2，…的匹配序列。

这里的关键是要意识到，对于这样的集合中的所有子序列， Start + Length将是相同的; 此外，来自不同集合的子序列将具有不同的Start + Length总和。 因此，让我们利用减少结果：

 // Obvious from the above .GroupBy(v => v.Start + v.Length) // We want to keep the longest subsequence. Since Start + Length is constant for // all, it follows the one with the largest Length has the smallest Start: .Select(g => g.OrderBy(u => u.Start).First()) 

这仍然会为userSelect中的每个单词留下尽可能多的匹配，就像该单词出现在original单词中一样。 所以，让我们把它减少到最长的比赛：

 .GroupBy(v => v.Word) .Select(g => g.OrderByDescending(u => u.Length).First()) 

我们现在有一个像{ Word = "the", Start = 0, Length = 3 } 。 让我们将其转换为userSelect的索引数组：

 .Select(w => Enumerable.Range(w.Start, w.Length).ToArray()) 

最后将所有这些arrays放在同一个集合中并完成任务！