按长度查找字符串的重复

Question

我有一串类似于下面所示的字母：

'ABTSOFDNSOHASAPMAPDSNFAKSGMOMAPEPTNSNTROMAPKSDFANSDHASOMAPDODDFG'

我将其视为密文，因此想开始查找重复的位置，以便找到加密密钥的长度（上面的示例是随机的，因此不会直接得到答案）

现在我想做的是编写一个代码，可以找到长度为 3 的重复项 - 例如 'MAP' 和 'HAS' 被重复。我希望代码找到这些重复，而不是我必须指定它应该查找的子字符串。

以前我用过：

text.find("MAP")

使用下面我写的答案：

substring = []
for i in range(len(Phrase)-4):
    substring.append(Phrase[i:i+4])
    
for index, value in freq.iteritems():
    if value > 1:
        for i in range(len(Phrase)-4):
            if index == Phrase[i:i+4]:
                print(index)

这给出了每个重复出现的子串的列表，理想情况下我希望它只是一个子串列表及其出现位置

Answer 1

Here what I did :)

import pandas as pd

# find frequency of each length 3 substring
Phrase    = "Maryhadalittlarymbada"
substring = []
for i in range(len(Phrase)-3):
    substring.append(Phrase[i:i+3])
Frequency  = pd.Series(substring).value_counts()

# find repetition's position in string
for index, value in Frequency.iteritems():
    positions = []
    if value > 1:
        for i in range(len(Phrase)-3):
            if index == Phrase[i:i+3]:
                positions.append(i)
        print(index, ": ", positions)
    else:
        continue

Answer 2

这是一个仅使用 built-ins

的解决方案

import itertools, collections
text = 'ABTSOFDNSOHASAPMAPDSNFAKSGMOMAPEPTNSNTROMAPKSDFANSDHASOMAPDODDFG'

创建一个函数，生成三个重叠块 - 灵感来自 pairwise function。

def three_at_a_time(text):
    '''Overlapping chunks of three.

    text : str
    returns generator
    '''
    a,b,c = itertools.tee(text,3)
    # advance the second and third iterators
    next(b)
    next(c)
    next(c)
    return (''.join(t) for t in zip(a,b,c))

用每个块的位置制作字典。

triples = enumerate(three_at_a_time(text))
d = collections.defaultdict(list)
for i,triple in triples:
    d[triple].append(i)

为具有多个位置的块过滤字典。

# repeats = itertools.filterfalse(lambda item: len(item[1])==1,d.items())
repeats = [(k,v) for k,v in d.items() if len(v)>1]

示例：

>>> for chunk in repeats:
...     print(chunk) 
... 
('HAS', [10, 51])
('MAP', [15, 28, 40, 55])
('OMA', [27, 39, 54])
('APD', [16, 56])
>>>

按长度查找字符串的重复

Finding repetitions of a string by length

python

string

substring

block-cipher

jupyter-notebook