Skip to main content
 首页 » 编程设计

python之在列表中查找重复子串

2025年04月02日10zhengyun_ustc

我有一长串子字符串(接近 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,那么我们就有了一个重复模式 :)