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

我正在尋找一些有效的方法（在.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

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

回答

相關問題