Mit KNUTH-MORRIS-PRATT Indizes von Mustern in einer Sequenz finden?

Question

Ich versuche, Muster in einer Folge von ganzen Zahlen zu finden. Ich habe das KNUTH-MORRIS-PRATT (KMP) in gefunden.

Ich habe die Funktion ein "Muster" in einem "Text" zu finden. Aber die Ausgabe der KMP Funktion ist ein Objekt. Ich brauche die Indizes für die Instanzen des Musters im Text. Ich habe versucht, die Attribute des Objekts zu überprüfen, indem Sie Punkt eingeben und Tab drücken, aber nichts ist da. Wie kann ich die Indizes bekommen?

bearbeiten

Code:

> # Knuth-Morris-Pratt string matching 
> # David Eppstein, UC Irvine, 1 Mar 2002 
> 
> from __future__ import generators 
> 
> def KnuthMorrisPratt(text, pattern): 
> 
>  '''Yields all starting positions of copies of the pattern in the text. Calling conventions are similar to string.find, but its 
> arguments can be lists or iterators, not just strings, it returns all 
> matches, not just the first one, and it does not need the whole text 
> in memory at once. Whenever it yields, it will have read the text 
> exactly up to and including the match that caused the yield.''' 
> 
>  # allow indexing into pattern and protect against change during yield 
>  pattern = list(pattern) 
> 
>  # build table of shift amounts 
>  shifts = [1] * (len(pattern) + 1) 
>  shift = 1 
>  for pos in range(len(pattern)): 
>   while shift <= pos and pattern[pos] != pattern[pos-shift]: 
>    shift += shifts[pos-shift] 
>   shifts[pos+1] = shift 
> 
>  # do the actual search 
>  startPos = 0 
>  matchLen = 0 
>  for c in text: 
>   while matchLen == len(pattern) or \ 
>    matchLen >= 0 and pattern[matchLen] != c: 
>    startPos += shifts[matchLen] 
>    matchLen -= shifts[matchLen] 
>   matchLen += 1 
>   if matchLen == len(pattern): 
>    yield startPos 

Sample Text: [1, 2, 2, 3, 3, 2, 4, 5, 2, 2, 3, 2] 
Sample Pattern: [2, 2, 3] 

Sample output: [1, 8] 

Answer 1

Sie sind nicht etwas von der Funktion zurückkehrt und Sie müssen durch den Iterator Schleife durch die Indizes erhalten comprehension verwenden. Schreibe es auf diese Weise:

from __future__ import generators 

def KnuthMorrisPratt(text, pattern): 

    pattern = list(pattern) 

    # build table of shift amounts 
    shifts = [1] * (len(pattern) + 1) 
    shift = 1 
    for pos in range(len(pattern)): 
     while shift <= pos and pattern[pos] != pattern[pos-shift]: 
      shift += shifts[pos-shift] 
     shifts[pos+1] = shift 

    # do the actual search 
    startPos = 0 
    matchLen = 0 
    for c in text:   
     while matchLen == len(pattern) or matchLen >= 0 and pattern[matchLen] != c: 
      startPos += shifts[matchLen] 
      matchLen -= shifts[matchLen] 
     matchLen += 1 
     if matchLen == len(pattern): 
      yield startPos 

    return matchLen 

t= [1, 2, 2, 3, 3, 2, 4, 5, 2, 2, 3, 2] 
p= [2, 2, 3] 
[k for k in KnuthMorrisPratt(t,p)] 

[1, 8]