KNUTH-MORRIS-PRATTを使用してシーケンス内のパターンのインデックスを取得していますか？

Question

私は整数のシーケンスでパターンを見つけようとしています。私はthis linkのKNUTH-MORRIS-PRATT（KMP）を見つけました。

私は関数を 'パターン'に入力して 'テキスト'で検索しました。しかし、KMP 関数の出力はオブジェクトです。テキストのパターンのインスタンスのインデックスが必要です。ドットを入力してタブを押すことでオブジェクトの属性をチェックしようとしましたが、何もありません。どのようにインデックスを取得できますか？

編集

コード：

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

あなたが関数から何かを返すされていない、あなたはcomprehensionを使用してインデックスを取得するイテレータをループする必要があります。この方法で書き直してください。

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]