代码之家 › 专栏 › 技术社区 › 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 Paul 16 年前

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

Diomidis Spinellis 16 年前

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

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前