c# - 如何在列表中找到子列表的索引？

Question

我正在寻找一些有效的方法(在 .NET 中)，如何查找某个字节列表中是否有字节序列，如果有，索引第一个开始的位置。

例如假设我有:

var sequence = new List<byte> { 5, 10, 2 };
var listOne = new List<byte> { 1, 3, 10, 5, 10, 2, 8, 9 };
var listTwo = new List<byte> { 1, 3, 10, 5, 2, 10, 8, 9 };

结果应该是我的序列在 listOne 中的索引 3 和 listTwo 中的索引 -1 上(即它不存在)。

当然，我可以逐个循环遍历列表 int 并从每个索引开始搜索，如果后面的数字与我的序列匹配，但有没有更有效的方法(例如使用扩展方法)？

Answer 1

这与子字符串搜索本质上是相同的问题(实际上，顺序很重要的列表是“字符串”的泛化)。

幸运的是，计算机科学长期以来经常考虑这个问题，所以你可以站在巨人的肩膀上。

看看文献。一些合理的起点是:

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

http://en.wikipedia.org/wiki/Rabin-karp

即使只是维基百科文章中的伪代码也足以很容易地移植到 C#。查看不同情况下的性能描述，并确定您的代码最有可能遇到哪些情况。 (我认为第一个原因是您所说的搜索关键字列表很短)。