-4

助けが必要です。次のような文字列に要素を格納するプログラムがあります。

"D,C,D,C,D,C,C,C,D,C,C,D,C"

そして、これらの要素を圧縮して、次のように画面に出力したいと思います。

(DC)3C(CDC)2

(DC)3 は、プログラムが文字列「DCDCDC」を圧縮したことを意味します。これは、DC が 3 回繰り返され、() 内の要素の各グループが最大 3 つの要素しか持てないことを意味します。

これまでのところ、同じタイプの要素のみをコンパクトにしました

"DDDCDCC"

の中へ：

D3CDC2

どんな助けでも喜んでいただければ幸いです。

4

1 に答える 1

2

もっと簡単なタスクで何をしようとしているのかを探ってみましょう。次の文字列内のDCまたはのインスタンスを折りたたみます。CDC

[D,C,D,C,D,C,C,C,D,C,C,D,C]

DCに現れるのでCDC、最初に長い文字列を実行する必要があります。CDC最初の文字から始めて、パターンが始まる場所を確認します。

DCDCDCCCDCCDC
 ^     ^  ^

これらの結果をそれぞれ折りたたむと、次のようになります。

D(CDCx1)DCC(CDCx2)

次に、次を確認しDCます。

D(CDCx1)(DCx1)C(CDCx2)

ええとああ！これはあなたの出力例にはなりませんでした! 別の順序で検索するとどうなるでしょうか。それぞれをマークすると、次のようDCになります。

DCDCDCCCDCCDC
^ ^ ^   ^  ^

これは次のように折りたたまれます。

(DCx3)CC(DCx1)C(DCx1)

ええと、それはあなたの出力にもなりません。

したがって、別の戦術を試すとどうなるか...最初から始めて、できるだけ早く任意のパターンに貪欲に一致させましょう。

DCDCDCCCDCCDC
^

CDCに匹敵できますか？いいえ、DCはどうですか？はい！

(DCx1)DCDCCCDCCDC
      ^

最初の交換後から、同じテストを行います。CDC？いいえ、DC？はい！

(DCx2)DCCCDCCDC
      ^

もう一度：CDC？いいえ、DC？はい！

(DCx3)CCDCCDC
      ^

CDC？いいえ、DC？いいえ、次の文字にスキップします。

(DCx3)CCDCCDC
       ^

CDC？はい！

(DCx3)C(CDCx1)CDC
              ^

CDC？はい！

(DCx3)C(CDCx2)
              ^

テキストの最後に到達しました。さらに、出力は期待値と一致しています。したがって、これを完全なアルゴリズムに拡張するには、可能なサブセットの完全なリストが必要です: CCC、CCD、CDC、CDD、DCC、DCD、DDC、DDD、CC、CD など。

幸運を！

于 2013-04-26T17:58:08.083 に答える