文字列が与えられ、文字列内の最大 Q 文字を変更できます。部分文字列 (それぞれ 2 文字の長さ) のリストと、対応するスコアも表示されます。文字列内に部分文字列が出現するたびに、合計スコアが加算されます。達成可能な最大スコアはいくつですか?
文字列の長さ <= 150、Q <= 100、部分文字列の数 <= 700
例：
文字列 = bpdcg
Q = 2
部分文字列:
bz - スコア: 2
zd - スコア: 5
dm - スコア: 7
NG - スコア: 10
この例では、文字列の "p" を "z" に、"c" を "n" に変更すると、最大スコア b を達成できます。したがって、新しい文字列は「bzdng」で、スコアは 2+5+10 = 17 です。
すでに文字が変更されている文字列が与えられた場合、スコアは、aho-corasick などの辞書マッチング アルゴリズムを使用して線形時間でチェックできることを知っています (または、少し複雑な Rabin Karp)。ただし、各 2 文字の置換を試行すると時間がかかりすぎて、チェックに時間がかかりすぎます。
私が考えた別の可能な方法は、逆方向に作業して、指定された部分文字列から理想的な文字列を作成し、元の文字列と最大 2 文字異なるかどうかを確認することでした。ただ、どうしたらよいかわかりませんし、できたとしても時間がかかりすぎると思います。
これについて最善の方法は何ですか？