栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

在大量字符串中找到长时间重复的子字符串

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

在大量字符串中找到长时间重复的子字符串

执行此操作的有效方法是创建子字符串的索引,并对它们进行排序。这是O(n lg n)运算。

BWT压缩执行此步骤,因此这是一个很好理解的问题,并且存在基数和后缀(要求O(n))排序实现,因此使其尽可能高效。仍然需要很长时间,大文本可能要花费几秒钟。

如果你想使用的工具代码,C ++

std::stable_sort()
进行
优于
std::sort()
自然语言(和比C的要快得多
qsort()
,但出于不同的原因)。

然后访问每个项目以查看其与相邻项目的公共子串的长度为O(n)。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/617033.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号