問題タブ [longest-substring]

最長の一般的な部分文字列の問題を解決する R パッケージを知っている人はいますか? ベクトルで動作する高速なものを探しています。

文字列のセットから最も長い共通のサブ文字列を見つけるためのPythonライブラリを探しています。この問題を解決するには、次の2つの方法があります。

• 接尾辞木を使用する
• 動的計画法を使用します。

実装された方法は重要ではありません。（2つの文字列だけでなく）文字列のセットに使用できることが重要です。

http://portal.acm.org/citation.cfm?id=1813708でアルゴリズムを実装しています。このアルゴリズムは、接尾辞配列を利用して最長の共通部分文字列を見つけます。アルゴリズムには、指定された文字列のセットをセンチネルと呼ばれる文字列区切り文字で連結した文字列のサフィックス配列を構築することが含まれます。たとえば、文字列 a、b、c が与えられた場合、新しい文字列 d が作成されます。これは a$1b$2c$3 で、ここで $1、$2、$3 は各文字列の末尾を示す番兵文字です。センチネル文字は一意で、a、b、c の他のすべての文字よりも辞書順で少なくなければなりません。

私の質問は、Python でのセンチネル キャラクターの表現に関するものです。a、b、および c が ASCII 文字列の場合、これらの文字列を UTF-8 に変換し、それらの範囲を 0 ～ 127 からより高い範囲にシフトして、使用可能な文字が、弦。それが合理的であると思われる場合、範囲が N-127+N (N は提供される文字列の数) になるように Python で文字を再マッピングするための最も効率的なメカニズムは何ですか?

リストを指定したpython関数が欲しい

文字列 'abc'、つまりリスト内のすべての要素に含まれる最長の部分を返します。mystring[0]最初の一致しない部分文字列が見つかるたびに、のスライスをループして残りの部分と比較し、ループから抜け出すソリューションがあります。ただし、これを行うには、より効率的でエレガントで Pythonic な方法が必要だと思います。

誰かがこれを適切に行う方法を指摘できますか?

問題：

私は3つの文字列s1、s2、s3を持っています。それぞれの両側にガベージテキストが含まれ、中央に定義パターンがありますtext1+number1。number1文字列ごとに2ずつ増加します。抽出したいtext1+number1。

私はすでに見つけるためのコードを書いていますnumber1

LCS関数を拡張してtext1を取得するにはどうすればよいですか？

例：

から"hello 5"、、取得"bolo 7"し"lo 9sdf"たい "lo 5"

コード：

簡単なLCS関数（テストケース）を書くことができましたが、この変更された関数を書くのに問題があります。

最長の単一のサブシーケンスだけでなく、rubyの文字列の配列からすべての一般的なサブシーケンスを見つけようとしています。

これは、入力が

["aaaF hello"、 "aaaG hello"、 "aaaH hello"]

期待される出力は

["aaa"、"こんにちは"]

私は最長の単一サブシーケンスアルゴリズムをいじっていますが、適切な出力を取得する方法を理解できません。ほとんどのアプローチの問題は、最終的な配列に「a」、「aa」、「h」、「he」、「hel」、「hell」などの他の要素があることです。

私はついに私が望むようにそれをしました。助けてくれてありがとう。宿題ではなかったことを強調したい。

バックグラウンド：

私は、コンピューターに保存されているすべての映画とテレビ シリーズのエピソードを繰り返し処理し、それらを (腐ったトマトを使用して) 評価し、評価順に並べ替えるプログラムを開発しています。

ファイル名から「.avi」や「720p」などの不要なテキストをすべて削除して、ムービー名を抽出します。

私はJavaを使用しています。

問題：

一部のフォルダには、次のようなムービー ファイルが含まれています。

しの301

しの302

「エピソード」という単語と数字は有効であり、映画でよく使用される単語であるため、単純に削除することはできません。ただし、「エピソード」と「3XX」を削除する必要があることは、名前の繰り返しの性質から明らかです。

別のフォルダーは次のようになります。

720p.S5.E1.不自由な戦い.avi

720p.S5.E2.towelie.avi

このような多くの 任意のパターンがさまざまなファイルのグループに存在します。キーワードを抽出できるように、これらの任意のパターンを再構成する何かが必要です。ケースごとに正規表現を書くのは現実的ではありません。

概要：

複雑な繰り返しパターンを見つけるために使用できるツールまたは API はありますか (数字のシーケンスを一致させる必要があります)? [最長共通配列ライブラリのようなもの]

LONGEST COMMON SUBSTRING 問題の最適化を手伝ってくれる人はいますか? 非常に大きなファイル (最大 2 Gb) を読み取らなければなりませんが、どの構造を使用すればよいかわかりません... C++ にはハッシュ マップはありません.TBB には同時ハッシュ マップがありますが、これを使用するのは非常に複雑です。アルゴリズム。**L 行列でこの問題を解決しましたが、貪欲で大きな入力には使用できません。マトリックスはゼロでいっぱいです。これは map> を使用してゼロ以外のみを保存することで排除できますが、これは非常に遅く、実際には使用できません。スピードは非常に重要です。コードは次のとおりです。

文字列から最長の単語を見つけることができるかどうかを尋ねる問題を見つけたとき、私はいくつかのアルゴリズムの問​​題に取り組み始めました（文字列には文字だけのスペースがありません）。しばらく考えた後、最大連続和問題と同様に、この問題に動的計画法を使用できるかどうかを確認したかっただけです。ここで、すべての文字を解析した後、isWordメソッド（すでに実装されています）を呼び出すことができます。次の文字に進み、単語の長さを増やす場合は、カウンターをゼロにリセットして、そのインデックスから単語を探し始めます。 。それが良いアプローチであるかどうかを教えてください。そうでない場合は、これを解決するためのより良いアプローチを教えてください。

助けてくれてありがとう。

-Vik