1

たとえば、次の文字列リストを生成するために、特殊文字（B、C、D、F、X、Z）によってランダムに生成される文字列があります。

B D Z Z Z C D C Z
B D C
B Z Z Z D X 
D B Z F
Z B D C C Z
B D C F Z
..........

生成文字列に一致し、最適なパターンを返し、文字列から文字列を抽出するパターン リストもあります。

文字列パターン

B D C [D must appear before the C >> DC]
B C F
B D C F
B X [if string have X,must be matched.]
.......

例えば、

B D Z Z Z C D C Z、それはBとを持っているDCので、B D C

D B Z C F、それはBandCを持っているFので、B C F

D B Z D F、それはBとを持っているFので、B F

.......

今、私はちょうど考えますsuffix array。

1.最初に文字列を接尾辞配列オブジェクトに変換します。

2.各パターンをループし、一致するサフィックス配列を見つけます。

3.一致したすべてのパターンを比較し、最適なパターンを取得します。

var suffix_array=Convert a string to suffix array.
var list=new List();
for (int i=0;i<pattern length;i++){
    if (suffix_array.match(pattern))
        list.Add(pattern);
}
var max=list[0];
for (int i=1;i<list.length;i++){
{
   if (list[i]>max)
      max=list[i];
      Write(list[i]);
}

このメソッドは複雑すぎると思います。パターンのツリーを構築し、それを取得してサフィックス配列と一致させる必要があります。もっとアイデアがある人はいますか?

====================アップデート

私は今、最善の解決策を得て、B、C、D、X ... の配列型のプロパティを持つ新しいクラスを作成します。各プロパティは、文字列に表示される位置を保存します。これで、文字列に B が表示されない場合は、この処理をすぐに終了できます。また、すべての C と D の位置を取得して、連続して表示できるかどうかを比較することもできます (DC、DCC、CCC....)。

4

2 に答える 2

0 
var suffix_array=Convert a string to suffix array.
var best=(worst value - presumably zero - pattern);
for (int i=0;i<pattern list array length;i++){
  if (suffix_array.match(pattern[i])){
    if(pattern[i]>best){
      best=pattern[i];
    }
    (add pattern[i] to list here if you still want a list of all matches)
  }
}
write best;

大まかに言って、とにかく、あなたが探しているものを理解していれば、それはわずかな改善ですが、より良い解決策があるかもしれないと確信しています。

于 2012-02-22T10:34:13.930 に答える
0

使用しているプログラミング言語がわかりません。正規表現でその機能を確認しましたか? これらに慣れていない場合は、Google にアクセスしてください。

于 2012-02-22T10:07:25.287 に答える