使用LINQ增加乐趣
经过几次尝试，我想出了一个纯LINQ解决方案，理论上可以成为一行代码。我尝试让它高效，但是功能性的解决方案会导致重复计算，因为你无法保持状态。
我们从一些预处理开始，以便稍后节省重复计算。是的，我知道使用索引可能是一个有问题的做法，但是如果你小心谨慎，它可以快速实现：
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之外完全是纯函数式的。当然，这也可以用函数式的方式编写：
var lookup = original.Select((s, i) => Tuple.Create)
.ToLookup(t => t.Item1, t => t.Item2);
它是如何工作的
在热身阶段，它创建了一个类似于字典的结构，将original中的每个单词与其在同一集合中出现的索引相关联。稍后将使用此结构从userSelect中的每个单词创建尽可能多的匹配序列（例如，“the”将导致两个匹配序列，因为它在original中出现了两次）。
然后：
.Where(lookup.Contains)
这很简单，它会从userSelect中删除所有不在original中出现的单词。
.SelectMany((s, i) => lookup[s]
.Select(j => new { User = userSelect.Skip(i), Original = original.Skip(j), Skipped = j })
.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() })
)
此时，我们已经将userSelect中的每个匹配单词投影到一个带有Start和Length属性的匿名对象中。然而，在匹配长度为N的序列中，还会导致长度为N-1、N-2等的更小的匹配序列。
关键在于意识到对于这些集合中的所有子序列，Start + Length将是相同的；此外，来自不同集合的子序列将具有不同的Start + Length之和。因此，让我们利用这一点来简化结果：
.GroupBy(v => v.Start + v.Length)
.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())
最后，将所有这些数组放入同一集合中，任务完成！
