IList<T>版本的String.IndexOf（查找子“字符串”，而不仅仅是单个对象）

Question

我正在寻找实现List<T>.IndexOf(List<T>)的方法。在.NET类库中，我只发现List<<T>.IndexOf(T)。

我有一个List longList和一个List possibleSubList。我想知道possibleSubList是否可以作为子“字符串”在longList中找到，如果可以，则返回longList中的索引。

这基本上与System.String.IndexOf相同。有人知道该如何称呼此功能或是否有其良好的实现方法吗？

伪代码示例：
{1, 2, 3, 9, 8, 7}.IndexOf({3, 9, 8}) = 2
{1, 2, 3, 9, 8, 7}.IndexOf({1, 2, 3, 9, 8, 7}) = 0
{1, 2, 3, 9, 8, 7}.IndexOf({2, 9}) = -1（未找到）


澄清：我已经有了一个简单直接的实现方法（两个嵌套的for循环），但是我的列表相当长，并且这是在性能敏感的区域。我希望找到比我的~O（m*n）更有效的实现方法。

- Seth

---

你能给出一些函数的预期用法、上下文和预期结果的例子吗？ - Jon Egerton

似乎Boyer Moore算法是一个不错的选择，但是基于T而不是char。我记不清复杂度了，但肯定比已经提出的选择要好（看起来像是一种暴力方法）。 - leppie

是的，朴素实现非常简单，但我希望能找到一个更高效算法的现有实现。 - Seth

你应该考虑更改标题，以包括关于高效实现的内容，因为似乎这是问题的主要目的（而不仅仅是像我所做的那样的天真实现）。 - docmanhattan

Answer 1

线性Z-Indexing可能是目前最快的子列表搜索算法之一，其中模式相同且语料库是动态的，具有真正的O(n)复杂度（对于小字母表，它比你从O(n)中期望的表现要好得多，因为ZIndexing提供了足够的机会跳过索引）：

我在中央佛罗里达大学Shaojie Zhang的遗传算法课程中编写了我的实现。我已经将算法适应于C#，特别是使用通用的IList<T>，如果您决定使用它，请给出信用。这些技术的研究可在此处找到，具体来说，请查看此处的讲义笔记。 无论如何，我已经在此处提供了代码 在TestZIndexing.cs中查看如何执行搜索的示例（在这种情况下，是在字符序列上进行搜索，但是使用泛型，您应该能够使用任何具有等号运算符的东西）。

使用方法很简单：

IEnumerable<int> LinearZIndexer.FindZ<T>(
        IList<T> patternSequence, IList<T> sourceSequence, bool bMatchFirstOnly)
        where T: IComparable;

而且，由于一些DNA是环形的，因此我有一个环形变体：

IEnumerable<int> LinearZIndexer.FindZCircular<T>(
        IList<T> patternSequence, IList<T> sourceSequence, bool bMatchFirstOnly)
        where T: IComparable;

更快速的方法：使用后缀树

如果你想要比O(n)更好的性能，可以使用后缀树来达到O(m)，其中m是模式列表的大小。当模式改变而语料库保持不变时（与先前情况相反），这个方法就起作用了。在我为TestSuffixTree.cs贡献的同一个库中查找。唯一的区别是你必须提前构建后缀树，因此它绝对适用于针对大型语料库的多模式搜索，但我为构建后缀树提供了一个O(n)和空间O(n)的算法。

调用同样简单，同样可以使用任何提供IComparable的东西：

string strTest = "bananabananaorangebananaorangebananabananabananaban";
string[] strFind = {"banana", "orange", "ban"};

// I use char, but you can use any class or primitive that 
// supports IComparable

var tree = new SuffixTree<char>();
tree.BuildTree(strTest.ToCharArray());
var results = tree.Find(str.ToCharArray());
foreach(var r in results) Console.WriteLine(r);

享受。

- Michael Hays

Answer 2

使用字符串搜索算法：（伪代码）

findsubstring(list<T> s, list<T> m){
    for(int i=0; i<s.length;++i)
        for(int j=0; j<m.length;++j)
            if(s[i] != s[j])
                break;
            if(j==m.length-1)
                return i;
    return -1;
}

- nulvinge

---

我目前是这样写的，希望有比O(N*M)更高效的实现方式。但知道它被称为字符串搜索算法对我来说很有帮助，可以寻找更好的实现方式（尽管我预计它们都会硬编码System.String）。 - Seth

这不是平均O(NM)的算法。实际上，它是O(Np*M)，其中p是s[i] == j[0]的概率。但这取决于你的数据。这是目前为止可用的最优算法（据我所知）。另一个给出的答案更糟糕... - nulvinge

嗯，有更快的方法，很有趣... 无论如何，这个算法在平均情况下是O(n+m)，就像你参考的维基页面上所说的那样。你处理什么类型的数据？ - nulvinge

@nulvinge 这个算法的下界是O（n+m），这意味着在找到目标之前，模式序列的第一个字符从未出现过。最坏情况是O（nm），平均情况与您所述的O（nmp）完全相同。无论如何，有更好的算法，其上限为O（n+m），对于非常长的序列，这变得非常重要。 - Michael Hays

http://en.wikipedia.org/wiki/String_search#Na.C3.AFve_string_search 中提到，平均时间复杂度为O(n+m)。我无法给出其他建议，因为我不知道您的数据是如何构建的，以及“非常长的序列”有多长，但我可以说这个算法在计算机上可以实现得非常快。由于它（可能）会受到内存限制，所以我敢说它可能是O(n/b)内存操作（其中b是块大小），除非您有一些非常不随机的数据和m<缓存大小。（作为一些趣闻：最内层循环的工作部分可以在x86上部分地实现为单个指令）。 - nulvinge

Answer 3

我认为您使用“子字符串”一词有些误导。我相信您正在尝试查看一个较大的列表是否包含与另一个列表中的所有元素相匹配的子序列元素。这是一个扩展方法，如果我正确理解您想要的内容，应该可以实现您想要的功能：

public static int IndexOfSequence<T>(this IEnumerable<T> longL, IEnumerable<T> subL)
    {
        var longList = longL.ToList();
        var subList = subL.ToList();

        int longCount = longList.Count;
        int subCount = subList.Count;

        if (subCount > longCount)
        {
            return -1;
        }

        int numTries = longCount - subCount + 1;

        for (int i = 0; i < numTries; i++)
        {
            var newList = new List<T>(longList.Skip(i).Take(subCount));

            if (newList.SequenceEqual(subList))
            {
                return i;
            }
        }

        return -1;
    }

然后你可以像这样使用它：

int index = longList.IndexOfSequence(possibleSubList);

- docmanhattan

---

不建议多次迭代IEnumerable。您可以调用ToList（）或缓存值。 - Markus Jarderot

嗨，docmanhattan，我使用 sub-'string' 来避免与一些算法名称中出现的数学定义子序列（http://en.wikipedia.org/wiki/Subsequence）混淆，例如 Longest Common Subsequence，它意味着完全不同的事情。 - Seth

@Seth 嗯，我认为你更有可能说“子序列”，因为子字符串仅涉及字符串，而你甚至已经得到了一个字符串搜索算法的答案 :-D - docmanhattan

@docmanhattan同意了。我在那个问题上犹豫了一下。非常感谢您的回复。但是，根据我理解您的代码，最坏情况下仍然是O(m*n)。由于我的longList会相当长，并且这是一个性能敏感的操作，我希望能够使用http://en.wikipedia.org/wiki/String_searching_algorithm中列出的更高效的算法。 - Seth

@Seth 你确定更聪明的算法值得吗？看起来这些解决方案涉及大量的预处理。你可以尝试让搜索将列表分成几个部分并并行搜索它们。太遗憾了，量子计算还没有到足以让我们同时进行所有序列测试的地步 :-D - docmanhattan