你能在c#中动态搜索字符串中的序列吗?

本文关键字:字符串 搜索 动态 | 更新日期: 2023-09-27 18:10:27

第一次在这里提问;

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

我之所以说动态,是因为我希望它能够搜索字符串并自己定位重复序列。我将无法提供一个序列的构造函数来查找。

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

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


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


从上面的例子中可以看到,在单个字符串中有两组匹配序列。如果有任何方法来识别这些编程,以及能够通过非常快地搜索这些不同的模式,它会帮助我显着!

匹配项很可能也会存储在List/array中以供以后使用。

谢谢你能提供的任何帮助!


编辑:正如这个问题所提出的,区分大小写将不是问题。

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

@HenkHolterman你是正确的,这将是一个压缩算法,然而,我不确定从哪里开始寻找我将匹配的序列。

我已经做了多次搜索类似的东西,但没有得到我正在寻找的答案。这就是为什么我的问题在这里被原样提出的原因。

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

你能在c#中动态搜索字符串中的序列吗?

这是蛮力的基本思想

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

要做到这一点,你基本上沿着这条线,使用正则表达式找到所有的T s,然后是所有的h s,等等…

  • 然后你找到所有大小为2的序列,所以你会找到所有的Th s, hi s和is s

  • 重复此操作,直到找到所有序列。

运行时为

    使用regex查找特定序列的时间复杂度:O(n)
  • 乘以特定大小的不同序列的数量:O(n)
  • 倍的大小:O(n)
总时间复杂度为O(n3)

使用后缀树在O(n)时间内完成此操作。我添加这个多余的句子是为了防止它被转换成注释