确定一个序列是否在另一个序列中的最佳方法？

Question

这是将“字符串包含子字符串”问题推广到（更多）任意类型的问题。

给定一个序列（例如列表或元组），确定另一个序列是否在其中的最佳方法是什么？另外，它应该返回子序列开始处的元素的索引：

用法示例（序列顺序）：

>>> seq_in_seq([5,6],  [4,'a',3,5,6])
3
>>> seq_in_seq([5,7],  [4,'a',3,5,6])
-1 # or None, or whatever

到目前为止，我只是依靠蛮力，它看起来缓慢，丑陋且笨拙。

Answer 1

我第二次使用Knuth-Morris-Pratt算法。顺便说一句，您的问题（和KMP解决方案）正是Python
Cookbook
2nd
Edition中的配方5.13
。您可以在http://code.activestate.com/recipes/117214/中找到相关代码。

它找到给定序列中的 所有 正确子序列，并应将其用作迭代器：

>>> for s in KnuthMorrisPratt([4,'a',3,5,6], [5,6]): print s
3
>>> for s in KnuthMorrisPratt([4,'a',3,5,6], [5,7]): print s
(nothing)