找到最长重复字母的位置

Question

我有一个包含字母的文件。我需要找到最长重复字母的位置。例如，如果文件包含aaassdddffccsdddfgssfrsfspppppppppppddsfs，我需要一个程序来查找ppppppppppp的位置。我知道我需要使用.index函数来找到位置但是我被卡在循环上。

Answer 1

使用itertools.groupby：

import itertools

mystr = 'aaassdddffccsdddfgssfrsfspppppppppppddsfs'

idx = 0
maxidx, maxlen = 0, 0
for _, group in itertools.groupby(mystr):
    grouplen = sum(1 for _ in group)
    if grouplen > maxlen:
        maxidx, maxlen = idx, grouplen
    idx += grouplen

给出idx和最长相同子字符串的长度：

>>> print(maxidx, maxlen)
25, 11

>>> mystr[25:25+11]
'ppppppppppp'

Answer 2

你需要遍历整个字符串。跟踪您遇到的每个新字母及其索引以及每个序列的持续时间。仅存储最大序列

s = 'aaassdddffccsdddfgssfrsfspppppppppppddsfs'

max_c = max_i = max_len = None
cur_c = cur_i = cur_len = None
for i, c in enumerate(s):
    if c != cur_c:
        if max_len is None or cur_len > max_len:
            max_c, max_i, max_len = cur_c, cur_i, cur_len
        cur_c = c
        cur_i = i
        cur_len = 1
    else:
        cur_len += 1
else:
    # One last check when the loop completes
    if max_len is None or cur_len > max_len:
        max_c, max_i, max_len = cur_c, cur_i, cur_len

print max_c, max_i, max_len

Answer 3

这是一个oneliner

from itertools import groupby
from functools import reduce
[(k, next(g)[0], sum(1 for _ in g)+1) for k, g in groupby(enumerate(
    'aaassdddffccsdddfgssfrsfspppppppppppddsfs'), key=itemgetter(1))] 

以上生成（键，位置，长度）。您可以通过应用reduce来获得最大长度

from itertools import groupby
from functools import reduce
from operator import itemgetter
reduce(lambda x,y:x if x[2] >= y[2] else y,
   ((k, next(g)[0], sum(1 for _ in g)+1) for k, g in groupby(enumerate(
    'aaassdddffccsdddfgssfrsfspppppppppppddsfs'), key=itemgetter(1))))

Answer 4

实现此目的的一种快速方法是使用正则表达式将重复字符与(.)(\1+)匹配。然后我们使用生成器理解循环所有这些结果，并根据长度（max）找到key=len。最后找到了最大的字符串，我们调用thestr.index()来查找发生最长重复字母的位置：

import re
txt = "aaassdddffccsdddfgssfrsfspppppppppppddsfs"
idx = txt.index(max((''.join(f) for f in re.findall(r"(.)(\1+)", txt)), key=len))
print(idx)

以下是分为几个阶段的相同代码：

>>> import re
>>> txt = "aaassdddffccsdddfgssfrsfspppppppppppddsfs"
>>> matches = list(''.join(f) for f in re.findall(r"(.)(\1+)", txt))
>>> print(matches)
['aaa', 'ss', 'ddd', 'ff', 'cc', 'ddd', 'ss', 'ppppppppppp', 'dd']
>>> longest = max(matches, key=len)
>>> print(longest)
ppppppppppp
>>> print(txt.index(longest))
25