我有一长串子字符串(接近 16000),我想找到重复循环开始/停止的位置。我想出了这段代码作为起点:
strings= ['1100100100000010',
'1001001000000110',
'0010010000001100',
'0100100000011011',
'1001000000110110',
'0010000001101101',
'1100100100000010',
'1001001000000110',
'0010010000001100',
'0100100000011011',]
pat = [ '1100100100000010',
'1001001000000110',
'0010010000001100',]
for i in range(0,len(strings)-1):
for j in range(0,len(pat)):
if strings[i] == pat[j]:
continue
if strings[i+1] == pat[j]:
print 'match', strings[i]
break
break
此方法的问题是您必须知道 pat 是什么才能搜索它。我希望能够从第一个 n 子列表(在本例中为 3)开始并搜索它们,如果不匹配,则将一个子字符串向下移动到下一个 3,直到它遍历整个列表或找到重复。我相信如果长度足够长(可能是 10),它会发现重复而不需要太长的时间。
请您参考如下方法:
strings= ['1100100100000010',
'1001001000000110',
'0010010000001100',
'0100100000011011',
'1001000000110110',
'0010000001101101',
'1100100100000010',
'1001001000000110',
'0010010000001100',
'0100100000011011',]
n = 3
patt_dict = {}
for i in range(0, len(strings) - n, 1):
patt = (' '.join(strings[i:i + n]))
if patt not in patt_dict.keys(): patt_dict[patt] = 1
else: patt_dict[patt] += 1
for key in patt_dict.keys():
if patt_dict[key] > 1:
print 'Found ' + str(patt_dict[key]) + ' repeating instances of ' + str(key) + '.'
试一试。在线性时间内运行。基本上使用字典来计算子集中出现 n 大小模式的次数。如果它超过 1,那么我们就有了一个重复模式 :)
