使用KNUTHMORRISPRATT获取序列中发现的模式的索引？

Question

我在尝试寻找整数序列中的模式。我在this link找到了KNUTH-MORRIS-PRATT（KMP）。你知道吗

我给函数提供了一个“模式”来在“文本”中查找，但是KMP的输出 函数是一个对象。我需要文本中模式实例的索引。我试着通过键入dot并按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]