如何在列表中查找子列表的索引？

我正在寻找一些有效的方法（在.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和指数-1指数3（即它不存在）的listTwo。

当然，我可以遍历列表int int和每个索引，并搜索下面的数字是否与我的序列匹配，但有没有更有效的方法（例如使用扩展方法）？

来源

2010-08-20 Lukáš Rubeš

当然，如果列表未排序，你将不得不迭代每个项目，直到找到序列？使用扩展方法或Linq不能奇迹般地提高效率。 – 2010-08-20 09:48:29

我相当怀疑有这种类型的扩展的.NET库。但你可以创建你自己的。 – 2010-08-20 09:58:05

我不得不补充说，我的序列很短（少数），但我搜索它的列表很长（数千个项目） – 2010-08-20 10:01:33

我建议将每个List<int>转换为String，然后使用String.IndexOf(sequence)进行搜索以确定序列在哪里或是否存在。

来源

2010-08-20 09:58:47 ChrisBD

Mmh我真的怀疑这会提高效率，因为你必须从列表中创建字符串更多的内存使用和更多的计算）。当然，它会让事情变得更容易，因为您不需要编写用于搜索子字符串的代码。 – digEmAll 2010-08-20 10:01:10

我也担心效率。但它肯定会更短，也许可读。 – 2010-08-20 10:04:41

如果您创建了扩展方法并对其进行了描述，那么它也将以简短和可读的方式代替使用情况。 – 2010-08-20 10:11:50

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

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

看看文献。一些合理的出发点是：

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

甚至只是在Wikipedia文章是伪足移植到C＃很容易。查看不同情况下的性能描述，并确定代码最有可能遇到哪些情况。（我正在考虑你所说的关于搜索关键字列表的短小的第一个问题）。

来源

2010-08-20 10:15:17

谢谢你的链接，我只是想知道，如果有任何方法实施。NET使用其中的一些算法，以节省我的时间，然后自己实施它们。 – 2010-08-20 10:35:35

'System.String.IndexOf'很有可能实现其中的一个！您将相同的算法应用于数据类型时，并不经常用于减少查找impl的机会。我确定在那里有一个地方，但发现它是另一回事。 – 2010-08-20 11:25:00

我觉得最彻底的方法是创建一个通用的扩展方法是这样的：

var indexOne = listOne.SubListIndex(0, sequence); 
var indexTwo = listTwo.SubListIndex(0, sequence);

附注：

public static int SubListIndex<T>(this IList<T> list, int start, IList<T> sublist) 
{ 
    for (int listIndex = start; listIndex < list.Count - sublist.Count + 1; listIndex++) 
    { 
     int count = 0; 
     while (count < sublist.Count && sublist[count].Equals(list[listIndex + count])) 
      count++; 
     if (count == sublist.Count) 
      return listIndex; 
    } 
    return -1; 
}

以这种方式来调用你也可以从一个给定的索引开始，如果你需要搜索更多的子列表出现

来源

2010-08-20 10:27:46 digEmAll

这正是我现在正在做的。但正如Jon Hanna所说，有更有效的子集搜索方法。我只是想知道如果我不在.NET中丢失一些东西。 – 2010-08-20 10:38:30

IMO这些算法不容易适用于非char字符串。例如，boyer-moore需要一个alphabeth大小的数组，并且对于Int32 alphabeth大小是2^32。 Rabin-karp使用哈希表示非实际字符串可能很难实现。可能唯一真正可用的是我猜的Knuth-Morris-Pratt，但我认为不会那么快...... – digEmAll 2010-08-20 11:41:24

如何在列表中查找子列表的索引？

回答

相关问题