我需要确定一个字符串中的所有子字符串具有最小的大小和重复。需要注意的是,我不希望返回的子字符串本身是其他返回的子字符串的子字符串。换句话说,子串的集合需要是不相交的集合。下面的函数可以工作,但效率很低。97.9%的时间花在重新计算后缀数组和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)
string_dict
{' string ':Substring(length=8,count=2),'this':String(length=4,count=2)}
1条答案
按热度按时间toiithl61#
在回答了@stef之后,我想我有了一个更好的方向。我很确定这可以改进,但它比原来快得多,可能是O(n log n)。