文字列内の部分文字列のすべての開始インデックスをオーバーラップしている部分を含めて高速に印刷する

Question

私はこの宿題に関する質問に答えようとしています。部分文字列の異なる出現は、互いに重なり合う可能性があります。

サンプル1

入力：

TACG

GT

出力：

説明：パターンは、長いテキストよりであるためには発生していませんテキスト

サンプル2

入力：

ATA

ATATA

出力：

0~2

説明：パターンは位置1および3に表示されます（これらの2つの出現はお互いに重なる）。

試料3

ATAT

GATATATGCATATACTT

出力：

説明：パターンは、テキスト内の位置1、3で表示され、9 。

私が提出してる答えは、このいずれかになります。

def all_indices(text, pattern): 
    i = text.find(pattern) 
    while i >= 0: 
     print(i, end=' ') 
     i = text.find(pattern, i + 1) 


if __name__ == '__main__': 
    text = input() 
    pattern = input() 
    all_indices(text, pattern) 

しかし、このコードは、最終的なテストケースを失敗している：

失敗した場合の＃64分の63：超過時間制限（使用時間：7.98/4.00、使用メモリ：77647872/536870912）

オンライン裁判官はピソで回答を送っていることを知っていますn、異なる言語の時間制限が異なります。

私は他の回答のためにかなり検索して近づいてきた：regexes、suffix trees、Aho-Corasick ...これまでのところ、それらのすべては、このシンプルなソリューションをアンダーパフォーム（findがimplemented in Cあるかもしれないので？）。

私の質問です。このタスクをより速く行う方法はありますか？

Answer 1

printがプログラムを最も遅くする場合は、できるだけ少なくするようにしてください。あなたの問題への迅速かつ汚いソリューション：

def all_indices(string, pattern): 
    result = [] 
    idx = string.find(pattern) 
    while idx >= 0: 
     result.append(str(idx)) 
     idx = string.find(pattern, idx + 1) 
    return result 

if __name__ == '__main__': 
    string = input() 
    pattern = input() 
    ' '.join(all_indices(string, pattern)) 

将来的には正しくあなたは、私がテストケースがされていたことを信じてpython profilers

Answer 2

を使用することができ、全体のプロセスを遅くしているあなたのコードの一部を識別するためにKnuth-Morris-Prattアルゴリズムに対してより寛大である。 https://en.wikibooks.org/wiki/Algorithm_Implementation/String_searching/Knuth-Morris-Pratt_pattern_matcher#Pythonからコピーされたこのコードは、すべてのケースをパスしました。

# Knuth-Morris-Pratt string matching 
# David Eppstein, UC Irvine, 1 Mar 2002 

#from http://code.activestate.com/recipes/117214/ 
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