3

ここで初めて質問します。

検索アルゴリズム、または組み込みメソッドを使用して、文字列内の繰り返しシーケンスまたはその他の変数を動的に検索できるようにする方法を探しています。

私が動的と言った理由は、文字列を検索して繰り返しシーケンスを独自に見つけられるようにしたいからです。検索するシーケンスのコンストラクターを提供することはできません。

これが可能かどうかはわかりませんが、可能であれば、すべての助けをいただければ幸いです!

これは私が探しているものの基本的な視覚的表現です(これはコードではなく、単なる文字列の例です)


これは、全体にシーケンスを持つ長い文字列になります。これには、一致する文字が並んでいる場合とそうでない場合がありますが、いずれにせよ、これは長い文字列になりますこれが長い文字列になる場合は、これらのシーケンスを単独で見つける必要があります。


上記の例からわかるように、1 つの文字列全体に 2 セットの一致するシーケンスがあります。これらの異なるパターンを非常に高速に検索できることに加えて、これらをプログラムで識別する方法があれば、非常に役立ちます!

一致は、後で使用するためにリスト/配列に保存される可能性が最も高いです。

あなたが提供できる助けをありがとう!


編集: この質問が尋ねられたので、大文字と小文字の区別は問題になりません。

2 つの一致があると述べたとき、2 つの特定のシーケンスに重複があることを意味しました。そのうちの 1 つには 2 つの重複がありました。

@HenkHoltermanこれが圧縮アルゴリズムになることは正しいですが、一致するシーケンスを探すためにどこから始めればよいかわかりませんでした。

これに似たものについて複数の検索を行っていましたが、探していた答えが不足していました. それが、私の質問がここにあるように提起された理由です。

これまでに得たすべての反応に感謝します!

4

2 に答える 2

1

これが基本的なブルートフォースのアイデアです

  • 最初に、同じサイズの繰り返しシーケンスをすべて見つけます1(最小サイズを任意のサイズに変更できます)。

これを行うには、基本的に下に移動し、正規表現を使用してすべての を検索しT、次にすべてのを検索しますh...

  • 次に、サイズ 2 のすべてのシーケンスを見つけるので、すべてのThs とhis とissが見つかります。

  • すべてのシーケンスが見つかるまでこれを繰り返します。

ランタイムは

  • 正規表現で特定のシーケンスを見つけるための時間の複雑さ: O(n)
  • 特定のサイズの異なるシーケンスの数の倍: O(n)
  • サイズの数の倍: O(n)

総時間計算量はO(n 3 )になります。

于 2013-04-23T18:15:29.663 に答える