首页 > 代码库 > 字符串问题python实现(二 )
字符串问题python实现(二 )
问题:求字符串中重复出现且长度最长子字符串,要求输出:符合条件子字符串、其重复出现次数、其首字母位置。
分析:后缀数组方法求解。
python版代码:
# 问题:求字符串中重复出现且长度最长子字符串,要求输出:符合条件子字符串、其重复出现次数、其首字母位置。 # 分析:后缀数组方法求解。 # by chasdmeng def build_suffix_array(suffix_array, text_string): for i in range(len(text_string)): suffix_array.append(text_string[i:]) suffix_array.sort() def comlen(str_a, str_b): max_len = 0 for i in range(1, len(str_a)+1): max_len = i if str_a[:i]==str_b[:i] else max_len return max_len def longset_repeat_substring(suffix_array, text_string): max_len, max_idx = 0, 0 t={} for i in range(len(text_string) - 1): com_len= comlen(suffix_array[i], suffix_array[i+1]) if com_len in t: t[com_len]+=1 else: t[com_len] = 2 [max_len, max_idx] = [com_len, i] if com_len > max_len else [max_len, max_idx] loc = [len(text_string)-len(suffix_array[max_idx + i]) + 1 for i in range(t[max_len])] loc.sort() return suffix_array[max_idx][:max_len], t[max_len], loc if __name__ == ‘__main__‘: suffix_array = [] text_string = "yyabcdabjcabceg" build_suffix_array(suffix_array, text_string) substring, time, location = longset_repeat_substring(suffix_array, text_string) print ‘\nIn \‘‘, text_string, ‘\‘, the longest string‘, ‘\‘‘, substring, ‘\‘occuers‘, time, ‘times‘,‘,the first character position‘, ‘,‘.join([str(i) for i in location]), ‘.‘
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。