2013-04-23 18 views
3

第一次在這裏問一個問題;你可以在c#中的字符串中動態搜索序列嗎?

我正在尋找一種方法能夠使用搜索算法或內置方法來動態搜索字符串或其他變量中的重複序列。

我說動態的原因是因爲我希望它能夠搜索字符串並自行定位重複序列。我不能夠提供一個序列的構造函數來尋找。

我不確定這是否可能,但如果是這樣,所有幫助將不勝感激!

這裏是我所期待的一個基本的可視化表示(請注意,這不是代碼,只是一個字符串的實例)


這將是一個很長的字符串那將會有整個序列。這可能並排匹配字符,也可能不匹配,但無論如何,這將是一個長字符串。如果這將是一個長字符串,我需要它自己找到這些序列


正如你可以通過上面的例子中看到的,有2套在整個單個字符串匹配序列。如果有任何方法可以通過編程方式來識別這些方法,並且可以通過這些不同的模式快速搜索,那麼它將對我有很大幫助!

這些匹配很可能會存儲在列表/數組中以備後用。

感謝您提供任何幫助!


編輯: 由於這個問題是問,大小寫不會是一個問題。

當我提到有兩個匹配時,我的意思是2個特定的序列,有一個重複。其中之一,有2個重複。

@HenkHolterman你是對的,這將是一個壓縮算法,但是,我不知道從哪裏開始尋找我將匹配的序列。

我一直在做關於類似的東西的多個搜索,但與我正在尋找的答案不盡相同。這就是爲什麼我的問題是以這種方式提出來的。

非常感謝您收到我迄今爲止收到的所有回覆!

+0

這是個不錯的問題。你能定義**序列**是什麼嗎?任何包含兩個空格的序列是什麼? – 2013-04-23 18:11:08

+0

你可以做蠻力我會認爲這將是關於** O(n^3)** – 2013-04-23 18:11:32

+1

這至少與壓縮算法有關。 – 2013-04-23 18:11:48

回答

1

這裏是基本的蠻力的想法

  • 首先你發現大小1的所有重複序列(你可以改變任何你想要的最小尺寸)。

要做到這一點,你基本上是往下走的路線,並使用正則表達式來找到所有的T S的,然後所有的h S,等...

  • 然後你發現所有大小爲2的序列,所以你會發現所有的Th S和hi S和is小號

  • 你重複,直到你發現所有的序列。

運行時將是

  • 時間複雜找到與正則表達式的特定序列:O(n)的一個特定大小的不同序列的
  • 次數:Ò (n)
  • 次數的大小:O(n)

的總時間複雜度會爲O(n )

+0

這種特殊的方法可能會很快嗎?我不熟悉正則表達式,所以我會研究這個!這是要通過char字符串通過字符?或者這是否會考慮完全自行尋找模式? – Justin 2013-04-23 18:22:13

+0

@Justin取決於你的快速定義。 'O(n^3)'可以表示運行該操作所花費的時間可以與您輸入的立方體的大小成比例。這通常不被認爲是非常快速的,但至少它不是NP硬 – 2013-04-23 18:25:40

+0

@Justin,速度會大大增加,你做出最小長度的模式,你正在尋找。我可以假設你不關心在一個字符串中找到所有「t」。所以,如果你知道你只關心8字節或更多的模式,那麼根據SamIam的回答,你將會有一個更快的過程。 – 2013-04-23 18:29:31

0

使用suffix tree爲此在O(n)的時間。我添加了這個額外的句子,以防止它被轉換成評論。

相關問題