KNUTH-MORRIS-PRATT를 사용하여 시퀀스의 패턴 색인을 얻는 중?

Question

정수 시퀀스에서 패턴을 찾으려고합니다. 나는 this link에 KNUTH-MORRIS-PRATT (KMP)를 발견했다.

'텍스트'에서 찾기 위해 '패턴'기능을 제공했습니다. 그러나 KMP 함수의 출력은 하나의 객체입니다. 텍스트의 패턴 인스턴스에 대한 색인이 필요합니다. 도트를 입력하고 Tab 키를 눌러 객체의 속성을 확인하려고했지만 아무 것도 없습니다. 색인을 어떻게 얻을 수 있습니까?

편집

코드 :

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