你能在c#中动态搜索字符串中的序列吗?
本文关键字:字符串 搜索 动态 | 更新日期: 2023-09-27 18:10:27
第一次在这里提问;
我正在寻找一种方法,能够使用搜索算法,或内置的方法来动态搜索字符串内的重复序列,或其他变量。
我之所以说动态,是因为我希望它能够搜索字符串并自己定位重复序列。我将无法提供一个序列的构造函数来查找。
我不确定这是否可能,但如果是,所有的帮助将是感激的!
这是我正在寻找的一个基本的视觉表示(请注意,这不是代码,只是一个字符串的实例)
这将是一个长字符串,其中将包含序列。这可能有匹配的字符并排,也可能没有,但无论如何,这将是一个长字符串。如果这将是一个长字符串,我需要它自己在整个中找到这些序列!
从上面的例子中可以看到,在单个字符串中有两组匹配序列。如果有任何方法来识别这些编程,以及能够通过非常快地搜索这些不同的模式,它会帮助我显着!
匹配项很可能也会存储在List/array中以供以后使用。
谢谢你能提供的任何帮助!
编辑:正如这个问题所提出的,区分大小写将不是问题。
当我提到有2个匹配时,我的意思是2个特定的序列,有一个重复。其中一个有两个副本。
@HenkHolterman你是正确的,这将是一个压缩算法,然而,我不确定从哪里开始寻找我将匹配的序列。
我已经做了多次搜索类似的东西,但没有得到我正在寻找的答案。这就是为什么我的问题在这里被原样提出的原因。
谢谢你到目前为止收到的所有回复!
这是蛮力的基本思想
- 首先找到大小为
1
的所有重复序列(您可以将最小大小更改为您想要的任何大小)。
要做到这一点,你基本上沿着这条线,使用正则表达式找到所有的T
s,然后是所有的h
s,等等…
-
然后你找到所有大小为2的序列,所以你会找到所有的
Th
s,hi
s和is
s -
重复此操作,直到找到所有序列。
运行时为
- 使用regex查找特定序列的时间复杂度:O(n)
- 乘以特定大小的不同序列的数量:O(n)
- 倍的大小:O(n)
使用后缀树在O(n)时间内完成此操作。我添加这个多余的句子是为了防止它被转换成注释