残念ながら、次の問題の名前はわかりませんが、よく知られている問題だと思います。問題を解決するための効果的なアルゴリズムを見つけたい。
S-入力文字列、K-いくつかの数値（1 <= K <= 26）とします。
問題は、K個の異なる文字しかないSの最長の部分文字列を見つけることです。この問題を解決するための最良のアルゴリズムは何ですか？
いくつかの例：
1）S = aaaaabcdef、K = 3、回答= aaaaabc
2）S = aaba、K = 2、回答= acaaまたはaaba
3）S = abcde、K = 5、回答= abcde
私はこの問題の解決策のスケッチを持っています。しかし、それは私には難しすぎるように思えます。また、2次の複雑さもあります。したがって、単一の線形パスで、同じ文字のシークエントを1つの適切なカウントで計算できます。次のステップは、K文字のみを含むセットを使用することです。使用法は似ています：
std::string max_string;
for (int i = 0; i < s.size(); ++i)
{
std::set<int> my_set;
std::string possible_solution;
for (int j = i; j < s.size(); ++j)
{
// filling set and possible_solution
}
if (my_set.size() == K && possible_solution.size() > max_string.size())
max_string = possible_solution;
}
表記法：
s=入力文字列、ゼロベースのインデックス
[start, end)=開始から終了までの入力の部分文字列（含むstartが除外する）end
k-substring=最大k個の異なる文字を含む部分文字列
アルゴリズム：線形の複雑さ O(n)
start = 0
result = empty string
find max(end): [start, end) is a k-substring
LOOP:
// please note in every loop iteration, [start, end) is a k-substring
update result=[start, end) if (end-start) > length(result)
if end >= length(s) then DONE! EXIT
increase start until [start, end) is a (k-1)-substring
increase end while [start, end] is a k-substring
ENDLOOP
startまたはendを増やすと、文字プールサイズ（kプロパティ）がそれぞれ減少または増加するかどうかを確認するには、count []配列を使用できます。ここで、count [c] =現在の部分文字列[start、end）でのcの出現数です。
C ++の実装：http：//ideone.com/i2JPCq
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加