高效提取无嵌套重复子串：单次SA与LCP计算优化咨询

我需要从字符串中识别出满足最小长度和重复次数要求的子串，且返回的子串集合必须是无嵌套、不相交的（即不会返回属于其他返回子串的子串）。

当前实现的函数可以完成这个功能，但效率极低——97.9%的耗时都花在重复计算后缀数组（SA）和最长公共前缀数组（LCP）上。当前方案通过移除已找到的最长子串后重新计算SA和LCP来保证无嵌套特性，我想知道是否存在仅计算一次SA和LCP的更高效实现方式？

当前实现代码 #

from typing import Dict, List, NamedTuple
import numpy as np
import pandas as pd
from pydivsufsort import divsufsort, kasai

class Substring(NamedTuple):
    length: int
    count: int

def find_unique_repeat_substrings(s: bytes, min_length: int = 20, min_repeats: int = 10) -> Dict[str, Substring]:

    string_dict = dict()
    K = len(s)

    while K>=min_length:
        sa = divsufsort(s)
        lcp = kasai(s, sa)
        K_loc = np.argmax(lcp)
        K=np.max(lcp)
        #calculate number of repeats
        loc = K_loc+1
        while lcp[loc]==K:
            loc += 1
        cnt = loc-K_loc+1
        longest_string = s[sa[K_loc]:sa[K_loc]+K]
        
        #add substring to dict
        if cnt >= min_repeats and K>=min_length:
            string_dict[longest_string.decode()] = Substring(length=K, count=cnt)
        
        #remove substring
        s = s.replace(longest_string, b"")  # Replacing with bytes
    return(string_dict)


s = "this string is repeated three times in this sentence. string string.".encode()
string_dict = find_unique_repeat_substrings(s,min_length = 4, min_repeats=2)
print(string_dict)

当前输出结果 #

{' string ': Substring(length=8, count=2), 'this': Substring(length=4, count=2)}

完全可以通过仅计算一次SA和LCP来实现需求，核心思路是：先一次性提取所有符合条件的重复子串，再通过「长优先、去重叠」的规则筛选出无嵌套不相交的集合。具体步骤如下：

1. 一次性计算SA和LCP数组 #

这是整个流程的唯一一次SA/LCP计算，后续所有操作都基于这两个数组完成。

2. 从LCP数组中提取所有候选重复子串 #

LCP数组中连续的高值区间对应一组共享长前缀的后缀，这些前缀就是重复子串。我们需要：

• 遍历LCP数组，找出所有连续的、长度≥min_length的区间；
• 对每个区间，确定对应子串的长度（即区间内LCP的最小值）、重复次数（区间内后缀的数量+1）；
• 记录每个子串的所有出现位置（通过SA数组中的后缀起始索引）。

3. 按优先级筛选无重叠子串 #

• 将候选子串按长度从大到小排序（长度相同则按重复次数从多到少），优先保留长串，避免嵌套；
• 维护一个标记数组，记录原字符串中已被选中子串占用的位置；
• 遍历排序后的候选子串，检查其所有出现位置是否与已标记区域无重叠：
  • 若完全不重叠，则将该子串加入结果集，并标记其所有出现的区间；
  • 若有重叠，则跳过该子串。

优化后的代码实现 #

from typing import Dict, List, NamedTuple, Tuple
import numpy as np
from pydivsufsort import divsufsort, kasai

class Substring(NamedTuple):
    length: int
    count: int

def find_unique_repeat_substrings(s: bytes, min_length: int = 20, min_repeats: int = 10) -> Dict[str, Substring]:
    n = len(s)
    if n < min_length:
        return {}
    
    # 仅计算一次SA和LCP
    sa = divsufsort(s)
    lcp = kasai(s, sa)
    
    candidates = []
    
    # 从LCP数组中提取所有符合条件的候选子串
    i = 0
    while i < len(lcp):
        current_lcp = lcp[i]
        if current_lcp < min_length:
            i += 1
            continue
        
        # 找到连续的LCP等于current_lcp的区间
        start_idx = i
        while i < len(lcp) and lcp[i] == current_lcp:
            i += 1
        end_idx = i - 1
        
        # 重复次数 = 区间内的后缀数量 + 1（SA中每个后缀对应一次出现）
        repeat_count = end_idx - start_idx + 2
        if repeat_count < min_repeats:
            continue
        
        # 获取子串内容
        substr = s[sa[start_idx]:sa[start_idx] + current_lcp].decode()
        # 记录所有出现的位置 (start, end)
        positions = []
        for idx in range(start_idx, end_idx + 2):
            pos_start = sa[idx]
            pos_end = pos_start + current_lcp
            positions.append((pos_start, pos_end))
        
        # 用负号实现降序排序（长度优先，其次重复次数）
        candidates.append((-current_lcp, -repeat_count, substr, current_lcp, repeat_count, positions))
    
    # 按长度降序、重复次数降序排序
    candidates.sort()
    
    # 标记已占用的区间
    occupied = [False] * n
    result = {}
    
    for _, _, substr, length, count, positions in candidates:
        # 检查所有出现位置是否未被占用
        valid = True
        for (start, end) in positions:
            if any(occupied[start:end]):
                valid = False
                break
        if valid:
            # 标记占用位置
            for (start, end) in positions:
                occupied[start:end] = [True] * (end - start)
            result[substr] = Substring(length=length, count=count)
    
    return result

# 测试示例
s = "this string is repeated three times in this sentence. string string.".encode()
string_dict = find_unique_repeat_substrings(s, min_length=4, min_repeats=2)
print(string_dict)

代码说明 #

• 仅调用一次divsufsort和kasai，彻底避免了重复计算的开销；
• 通过LCP数组的连续区间提取所有候选重复子串，确保不遗漏符合条件的子串；
• 长串优先的排序规则保证了不会出现嵌套子串（长串被选中后，其内部的短串会因位置被占用而被排除）；
• 占用标记数组严格确保了子串之间不相交。

内容的提问来源于stack exchange，提问作者Eric