IList <T>版本的String.IndexOf(找到一个子串',而不仅仅是一个对象)

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
{1, 2, 3, 9, 8, 7}.IndexOf({1, 2, 3, 9, 8, 7}) = 0
{1, 2, 3, 9, 8, 7}.IndexOf({2, 9}) = -1 (not found)


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

Answer 1

线性Z-Indexing可能是目前最快的子列表搜索算法之一,其中模式相同,语料库是动态的,具有真正的O(n)复杂度(使用小字母表,它的表现比你预期的要好得多) (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)和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);

请享用.