c# - String.IndexOf 的 IList 版本(找到一个子 -'string' ，而不仅仅是单个对象)

Question

我正在寻找 List<T>.IndexOf(List<T>) 的实现.我只找到了 List<<T>.IndexOf(T)在 .NET 类库中。

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

这与 System.String.IndexOf 的语义基本相同.任何人都知道如何调用它或者它是否有很好的实现方式？

伪代码示例:

{1, 2, 3, 9, 8, 7}.IndexOf({3, 9, 8}) = 2<br/>
{1, 2, 3, 9, 8, 7}.IndexOf({1, 2, 3, 9, 8, 7}) = 0<br/>
{1, 2, 3, 9, 8, 7}.IndexOf({2, 9}) = -1 (not found)<br/>


澄清:我已经有了一个直接的实现(两个嵌套的 for 循环)，但我的列表相当长，而且这是一个性能敏感区域。我希望找到比我的 ~O(m*n) 更有效的实现。

Answer 1

线性 Z 索引 可能是当今最快的子列表搜索算法之一，其模式相同且语料库是动态的，具有真正的 O(n) 复杂度(小字母，由于 ZIndexing 提供了大量跳过索引的机会，因此它的性能比你对 O(n) 的预期要好得多:

我在中央佛罗里达大学的 Shaojie Zhang 的指导下，在遗传算法课上编写了我的实现。我已将算法改编为 C#，特别是使用通用 IList<T> ，如果您决定使用它，请给予信任。这些技术的研究可用here ，具体看讲义here .

无论如何，我已经提供了代码 here

在 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) 和 Space(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);

享受吧。