3

第一次在这里提问;

我正在寻找一种能够使用搜索算法或内置方法来动态搜索字符串或其他变量中的重复序列的方法。

我说动态的原因是因为我希望它能够搜索字符串并自行定位重复序列。我将无法提供要查找的序列的构造函数。

我不确定这是否可能,但如果是,所有帮助将不胜感激!

这是我正在寻找的基本视觉表示(请注意,这不是代码,只是一个字符串的例子)


这将是一个很长的字符串,整个字符串都有序列。这可能有并排匹配的字符,也可能没有,但无论如何,这将是一个长字符串。如果这将是一个长字符串,我需要它自己在其中找到这些序列


正如您在上面的示例中所看到的,整个单个字符串中有 2 组匹配序列。如果有任何方法可以以编程方式识别这些,并且能够非常快速地搜索这些不同的模式,这将对我有很大帮助!

匹配项很可能也存储在列表/数组中以供以后使用。

感谢您提供的任何帮助!


编辑: 当这个问题被问到时,区分大小写不会成为问题。

当我提到有 2 个匹配项时,我的意思是 2 个特定的序列有重复。其中之一,有2个重复。

@HenkHolterman您说得对,这将是一种压缩算法,但是,我不确定从哪里开始寻找要匹配的序列。

我一直在对类似的事情进行多次搜索,但没有找到我正在寻找的答案。这就是为什么我的问题按原样在这里提出的原因。

谢谢你到目前为止我得到的所有回复!

4

2 回答 2

1

这是基本的蛮力想法

  • 首先,您会找到所有重复的大小序列1(您可以将最小大小更改为您想要的任何内容)。

要做到这一点,你基本上走下线,并使用正则表达式来查找所有的Ts,然后是所有的hs,等等......

  • 然后你找到所有大小为 2 的序列,所以你会找到所有的Ths 和his 和iss

  • 你重复这个直到你找到所有的序列。

运行时将是

  • 使用正则表达式查找特定序列的时间复杂度: O(n)
  • 乘以特定大小的不同序列的数量: O(n)
  • 乘以大小数: O(n)

总时间复杂度为O(n 3 )

于 2013-04-23T18:15:29.663 回答
0

使用后缀树在 O(n) 时间内完成此操作。我正在添加这个无关的句子,以防止将其转换为评论。

于 2013-04-24T04:58:33.870 回答