Best way to determine if a sequence is in another sequence?

by

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/

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)

More Related Contents:

  1. How do i implement these algorithms below
  2. finding the biggest sequence of repeating numbers in a list
  3. How to efficiently compare two unordered lists (not sets) in Python?
  4. Change the name of a key in dictionary
  5. Convert Python sequence to NumPy array, filling missing values
  6. How to split text without spaces into list of words
  7. Approximating data with a multi segment cubic bezier curve and a distance as well as a curvature contraint
  8. Weighted random selection with and without replacement
  9. What is the fastest way to flatten arbitrarily nested lists in Python? [duplicate]
  10. Understanding recursion in Python
  11. Efficient calculation of Fibonacci series
  12. How did Python implement the built-in function pow()?
  13. Find longest repetitive sequence in a string
  14. Python string ‘in’ operator implementation algorithm and time complexity
  15. Simple Python Challenge: Fastest Bitwise XOR on Data Buffers
  16. Algorithm to find which number in a list sum up to a certain number
  17. Checking if all elements in a list are unique
  18. When splitting an empty string in Python, why does split() return an empty list while split(‘\n’) returns [”]?
  19. Get number of items from list (or other iterable) with certain condition
  20. Weighted random sample in python
  21. What is the complexity of the sorted() function?
  22. What’s the algorithm of ‘set.intersection()’ in python?
  23. How to incrementally sample without replacement?
  24. Replace list of list with “condensed” list of list while maintaining order
  25. Python Weighted Random [duplicate]
  26. How can I interleave or create unique permutations of two strings (without recursion)
  27. Python: powerset of a given set with generators [duplicate]
  28. Handling big numbers in code
  29. What is this odd sorting algorithm?
  30. counting combinations and permutations efficiently

Leave a Comment