0

{A,B}いくつかのシーケンスを含み、シーケンス内の各文字が少なくとも 1 回出現すると仮定しましょう。要件を満たすシーケンス内の部分文字列を見つける方法:

  • A の数と B の数は可能な限り高い比率にする必要があります (#A/#B --> 最大)
  • 同じ比率の部分文字列が多数ある場合は、可能な限り長い部分文字列を返す必要があります
  • 最後に、同じ長さのものが多数ある場合は、開始インデックスが小さいものを返す必要がありました

出力として、見つかった部分文字列の先頭のインデックスとその長さが必要です。

例

IN: AAABAA
OUT: index = 0, length = 6 (ratio is 5 : 1)
IN: BABAABBA
OUT: index = 1, length = 4 (ratio is 3 : 1)

問題にアプローチする方法のヒントはありますか?

リクエストとして、私は私の考えを追加しています：

  1. 連続する A の 2 つのグループが 3 つ以上の B で区切られている場合、それ以上テストする理由はありません。...A{k}BBBA{m}...次のような部分文字列がある場合、比率は(k+m):3一方k:1またはm:1より良いオプションを提供する必要があるため、非常に単純です。

  2. また、A の最も長い部分文字列をすべて順番に見つけようとしました。私のシーケンスが次のようになる可能性が非常に高いと思いA{N1}BA{N2}BA{N3}ましたが、後で、たとえば必ずしもそうではないことがわかりました。

    ババアアアア

ご覧のとおり、同じ比率の 2 つのシーケンスがあります。

  1. i=1 長さ=4
  2. i=6 長さ=4

しかし、ルール 3 が意味するように、最初の 1 つを返さなければならないことを意味します。私のアルゴリズムは、シーケンス内で最も長く連続する A に基づいていると述べたからです。

4

1 に答える 1