确定一个序列是否在另一个序列中的最佳方法？ [英] Best way to determine if a sequence is in another sequence?

问题描述

这是字符串包含子字符串问题到（更多）任意类型的概括。

This is a generalization of the "string contains substring" problem to (more) arbitrary types.

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

Given an sequence (such as a list or tuple), what's the best way of determining whether another sequence is inside it? As a bonus, it should return the index of the element where the subsequence starts:

示例用法（序列中的序列）：

Example usage (Sequence in Sequence):

>>> 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

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

So far, I just rely on brute force and it seems slow, ugly, and clumsy.

推荐答案

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

I second the Knuth-Morris-Pratt algorithm. By the way, your problem (and the KMP solution) is exactly recipe 5.13 in Python Cookbook 2nd edition. You can find the related code at http://code.activestate.com/recipes/117214/

它会在给定序列中找到 all 个正确的子序列，并应将其用作迭代器：

It finds all the correct subsequences in a given sequence, and should be used as an iterator:

>>> 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)

这篇关于确定一个序列是否在另一个序列中的最佳方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！