如何用數組搜索數組？

我有2個字節數組：如何用數組搜索數組？

Dim A() As Byte = {1, 2, 3, 4, 5, 6, 7, 8, 9} 
    Dim B() As Byte = {5, 6, 7}

現在我想找到完整的B在一個的次數。我嘗試Array.IndexOf（A，B）沒有運氣。有沒有一種簡單的方法來搜索數組，而不需要使用任何循環？

它應該以與B（）中相同的順序找到5,6,7的索引（位置）。如果A（）包含{1,2,3,4,7,6,5,9}，它應該返回false或-1，因爲它們的順序不同。

來源

2011-09-08 MilMike

幾乎相同：http://stackoverflow.com/questions/1020438/c-array-subset-fetching – Stefan

「沒有任何循環」是不可能的。由於數組可以是任何大小，因此無法從數組中獲取多個值。你的意思是沒有明確的代碼循環？ –

@斯特凡，謝謝！這很快，而且效果很好。 :) – MilMike

以下LINQ的語句將給出含有IEnumerable<int> B在一個位置（或空如果沒有發生就設置）：

Enumerable 
    .Range(0, 1 + a.Length - b.Length) 
    .Where(i => a.Skip(i).Take(b.Length).SequenceEqual(b));

我不知道如何轉換到VB.NET。

來源

2011-09-08 08:52:06 spender

W00t w00t。 20K！ – spender

這種方法看起來不錯，但速度很慢。對於100000個元素，在字節（）中爲16秒，但對較小的尺寸是有利的。長度也應該+1（至少在VB.NET中），因爲如果元素在列表的末尾，他們不會被發現，這裏是正確的版本： Enumerable.Range（0，A.Length （B.Length + 1）.Where（函數（i）A.Skip（i）.Take（B.Length）.SequenceEqual（B）） – MilMike

@qxxx：你說得對。固定。確實有更快的方法來做到這一點，即Knuth-Morris-Pratt，但是我已經掛上了（明確的）循環要求。 – spender

如何創建一個方法：

Concatinates搜索列表中的元素，將一個字符串
Concatinates列表的元素來搜索一個字符串
看起來第一個字符串中第二串的precense

像這樣：

public bool IsSubSetOf(IList<int> list1, IList<int> list2){ 
    var string1 = string.Join("", list1); 
    var string2 = string.Join("", list2); 
    return string1.Contains(string2); 
}

未測試...

來源

2011-09-08 08:39:54

這對{1，11，111，11，11}和{1，1，1}都是破的，比方說。 – Gleno

這是一個好主意（沒有顯式循環！），但會在很多情況下破壞。您可能需要在每個值周圍添加分隔符*（也在第一個和最後一個之前）以使其完美無缺地工作，這比string.Join提供的稍微複雜一些。你還需要返回一個索引，而不僅僅是一個布爾值--OP表示「找到」而不是「確定是否」。這個答案可以擴展到工作，但我不會把它作爲一個閱讀練習:) –

我站在糾正......但它仍然是一些辦法。 –

解決此問題的有效方法一般是KMP algorithm。快速使用Google提示可能會發現.NET實現here。它的實現僞代碼可從Wikipedia獲得。

低效，但無害地易於編碼方式中的鏈路中的一個被呈現以上如下：

int[] T = new[]{1, 2, 3, 4, 5}; 
int[] P = new[]{3, 4}; 

for (int i = 0; i != T.Length; i++) 
{ 
    int j = 0 
    for (;i+j != T.Length && j != P.Length && T[i+j]==P[j]; j++); 
    if (j == P.Length) return i; 
}

來源

2011-09-08 08:45:20 Gleno

這可能會實現，但它是C＃和使用一個循環：

private static int[] GetIndicesOf(byte[] needle, byte[] haystack) 
{ 
    int[] foundIndices = new int[needle.Length]; 

    int found = 0; 

    for (int i = 0; i < haystack.Length; i++) 
    { 

     if (needle[found] == haystack[i]) 
     { 
      foundIndices[found++] = i; 

      if (found == needle.Length) 
       return foundIndices; 
     } 
     else 
     { 
      i -= found; // Re-evaluate from the start of the found sentence + 1 
      found = 0; // Gap found, reset, maybe later in the haystack another occurrance of needle[0] is found 
      continue; 
     } 
    } 

    return null;    
}

測試與輸入：

Byte[] haystack = { 5, 6, 7, 8, 9, 0, 5, 6, 7 }; 
Byte[] needle = { 5, 6, 7 }; 
// Returns {0, 1, 2} 

Byte[] haystack = { 5, 6, 0, 8, 9, 0, 5, 6, 7 }; 
Byte[] needle = { 5, 6, 7 }; 
// Returns {6, 7, 8} 

Byte[] haystack = { 5, 6, 0, 7, 9, 0, 5, 6, 8 }; 
Byte[] needle = { 5, 6, 7 }; 
// Returns null 

Byte[] haystack = { 1, 2, 1, 2, 2 }; 
Byte[] needle = { 1, 2, 2 }; 
// Returns {2, 3, 4} 

Byte[] haystack = { 1, 2, 1, 2, 1, 2, 3 }; 
Byte[] needle = { 1, 2, 1, 2, 3 }; 
// Returns {2, 3, 4, 5, 6} 

Byte[] haystack = { 1, 1, 1, 1, 2 }; 
Byte[] needle = { 1, 2 }; 
// Returns {3, 4}

但LINQ的實施@spender的看起來更好。 :-P

來源

2011-09-08 08:54:27 CodeCaster

+1。奉承讓你無處不在！ – spender

對於heystack = {1，2，1，2，2}和needle = {1,2,2}，這顯然被破壞了。如果你每次都回溯needle.length，它可能會有效。 – Gleno

這是非常快速的我需要的，但沒有測試它與Gleno的問題 – MilMike

我採取的是：

public static int Search<T>(T[] space, T[] searched) { 
    foreach (var e in Array.FindAll(space, e => e.Equals(searched[0]))) { 
    var idx = Array.IndexOf(space, e); 
    if (space.ArraySkip(idx).Take(searched.Length).SequenceEqual(searched)) 
     return idx; 
    } 
    return -1; 
} 

public static class Linqy { 
    public static IEnumerable<T> ArraySkip<T>(this T[] array, int index) { 
    for (int i = index; i < array.Length; i++) { 
     yield return array[i]; 
    } 
    } 
}

一如往常，這取決於你的數據，這是否是「足夠好」，或者你將不得不採取更加複雜而高效的算法。我引入了一個數組跳轉，因爲Linq跳轉實際上只承擔IEnumerable接口，並且枚舉到索引。

來源

2011-09-08 08:58:59 flq

如何用數組搜索數組？

回答

相關問題