c# - 用其他子数组替换所有子数组的高效算法

Question

我有一个字节数组(可以变得非常大，超过 3200 万字节)，我需要用相同长度的其他子数组替换一些子数组。 我目前的方法是在字节数组中搜索我需要替换的所有子数组，每次我找到一个时将子数组的索引添加到列表中，然后继续。

我的代码如下。我有一种挥之不去的感觉，这效率不高，因为 3200 万字节需要超过 10 秒才能完成搜索和替换。我将 8 个字符串传递给它来替换，所以它基本上最终会搜索 16 个子数组。
有人看到我的算法有任何缺陷或更有效的算法吗？

附言我实际上并没有在此代码中替换它们，只是找到索引。我的代码应该非常高效。

 public class Search
{
    public List<int> positions;
    public List<int> lengths;
    private List<byte[]> stringsToSearchFor;
    public Search(List<string> strings){
        stringsToSearchFor = new List<byte[]>();
        positions = new List<int>();
        lengths = new List<int>();
        foreach (string tempString in strings){
            stringsToSearchFor.Add(Encoding.ASCII.GetBytes(tempString));
            stringsToSearchFor.Add(Encoding.Unicode.GetBytes(tempString));
        }
    }

    public void SearchBytes(byte[] haystack){
        int[] arrayOfInt = new int[stringsToSearchFor.Count];
        bool[] arrayOfBoolean = new bool[stringsToSearchFor.Count];
        for (var i = 0; i < haystack.Length; i++){
            byte currentByte = haystack[i];
            for (int stringCounter = 0; stringCounter < arrayOfBoolean.Length; stringCounter++)
            {
                byte[] stringLookFor = stringsToSearchFor.ElementAt(stringCounter);
                byte currentStringByte = stringLookFor[arrayOfInt[stringCounter]];
                //Saying the current byte is the desired one
                if (currentStringByte == currentByte)
                {
                    if (arrayOfInt[stringCounter] + 1 == stringLookFor.Length){
                        positions.Add(i - stringLookFor.Length + 1);
                        lengths.Add(stringLookFor.Length);
                        arrayOfInt[stringCounter] = 0;
                    }
                    else
                    {
                        arrayOfInt[stringCounter]++;
                    }
                }
                else
                {
                    arrayOfInt[stringCounter] = 0;
                }
            }
        }
        return;
    }



}

Answer 1

从 SearchBytes() 只有 2 个嵌套的 for 循环这一事实可以看出，这种暴力搜索算法有一个错误。这种暴力搜索需要 3 个嵌套循环:对于 haystack 中的每个起始位置，对于每个针串，您需要一个循环来检查整个针是否出现在 haystack 中的那个位置。 (如果发现字符不匹配，这个最内层的循环可能会提前中止。)

这是一个具体的例子:如果干草堆是ABCABCABD，而你的一根针线是ABCABD，那么这个字符串将不会被找到，尽管它确实出现了.那是因为一旦你的算法在大海捞针中看到第二个 C，它就会得出结论，它必须从大海捞针中的当前位置开始寻找针头，当在事实上它需要从更早的位置开始寻找。

无论如何，在长度为 n 的干草堆字符串中搜索单个长度为 m 的针字符串的暴力时间复杂度是 O(nm)，如果两者都中等长度，这是非常糟糕的。 John Kurlak suggested Knuth-Morris-Pratt or Rabin-Karp , 如果您正在寻找一些大字符串，那么运行其中任何一个肯定会加快速度(以及正确 :-P)，但是专门针对有效查找多个字符串的算法 字符串中的一个字符串称为Aho-Corasick algorithm .它需要时间 O(n+s+k)，其中 n 是干草堆的大小，s 是要搜索的针串大小的总和，k 是任何针串的出现次数 - 这很漂亮很难被击败。