代码之家 › 专栏 › 技术社区 › Greg

如何检测字符串列表中的重复?

analysis string algorithm

Greg · 技术社区 · 16 年前

我有一系列的SQL调用,我想用它们来检测循环(因此不必要的重复SQL调用),但它让我想到了这个更普遍的问题。

给出一个列表,比如 [a,b,c,b,c,a,b,c,b,c,a,b,b]

有什么办法可以把它变成 a,[[b,c]*2,a]*2,b*2

或者, [a,[b,c]*2]*2,a,b*2

也就是说,检测重复(可能是嵌套的重复)。

4 回复 | 直到 16 年前

Yuval F 16 年前

窥视 Lempel-Ziv-Welsh compression algorithm . 它建立在检测字符串中的重复并利用它们进行压缩的基础上。我相信你可以用 Trie 为了它。

Bombe 16 年前

我不是这个领域的专家,但您可能想看看一些压缩算法,在我看来,这正是它们所做的。

Toon Krijthe 16 年前

如果你能先对它排序,那么你很容易再进行一次查找重复的跑步记录。当然,像SQL查询这样的自由形式的排序听起来有点可怕。

Diomidis Spinellis 16 年前

如果字符串足够大,一种有趣的方法是在其上运行压缩工具(如gzip、bzip或7zip)。这些工具通过定位重复(在不同级别)并用指向文本第一个实例(或字典)的指针替换它们来工作。你得到的压缩是对重复的一种度量。转储文件(您必须编写代码才能完成此操作)将提供重复的内容。

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

5 月前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

6 月前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

6 月前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

6 月前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

7 月前

b39b332d · 使用C++标准库实现高效间隔存储

10 月前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

10 月前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

11 月前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

11 月前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

11 月前