1

文字列ファイルのリストを調べて、それらの間で最も一般的な部分文字列を報告するスクリプトを作成しようとしています。

例えば：

  1. こんにちは、弦一です。私はリンゴとオレンジが好きです。ここでは私たちはすべてひもです。
  2. こんにちは、二弦です。私はリンゴとオレンジが好きです。ここでは私たちはすべてひもです。
  3. こんにちは、弦三です。私はリンゴとオレンジが好きです。ここでは私たちはすべてひもです。
  4. こんにちは、四弦です。私はリンゴとオレンジが好きです。私は自分の個性を表現するのが好きです。

特定のしきい値 (たとえば、5 文字) を超える、文字列間の共通要素は何かをスクリプトに教えてもらいたいと思います。

言われるのが理想です

  • 「リンゴとオレンジが好き」がすべてのファイルに発生
  • 「こんにちは、文字列です」がすべてのファイルで発生する
  • 「We are all strings here」は 3 つのファイルで発生します。

SQL、Javascript、PHP、Ruby、Bashなど、私がよく知っているテクノロジーでこれを行う関数が存在する場合、私は非常に満足しています...

どうもありがとう、

ジャック

4

1 に答える 1

2

これは、 Longest common subsequence problemとして知られる難しい問題です。

動的プログラミングを使用したアルゴリズムの Python 実装を次に示します: http://www.algorithmist.com/index.php/Longest_Common_Subsequence

標準ライブラリ (C、Java、PHP、Python、Javascript、Ruby など) にそのような関数が付属しているとは思いません。ただし、ここで実装を探すことができます: http://www.google.com/codesearch?q=%22longest+common+subsequence%22

于 2011-01-13T16:59:24.183 に答える