しばらくの間、私はこの一見非常に単純な問題に頭を悩ませようとしてきました。文字列kが与えられた場合、その文字列kをk1 + k2 + k3 = kのように正確に3つの部分文字列k1、k2、k3に分割する最適な方法を見つける必要があります。分割は、各部分文字列を逆にしてそれらを結合し直すことによって、辞書式順序で可能な限り最小の結果が得られる場合にのみ最適です。
たとえば、文字列k = "anakonda"を取ります。それを分割する最適な方法は、k1 = "a"、k2 = "na"、k3 = "konda"です。これは、反転後（k1 = "a"、k2 = "an"、k3 = "adnok"）、k1 +を取得するためです。 k2 + k3 = "aanadnok"は、辞書式順序で可能な最小の結果です。
私の最初のアプローチは、常に次の辞書式最小文字で部分文字列を終了することでした。
std::string str = "anakonda"
int first = find_min(str, 0, str.size() - 3); // Need to have at least 3 substrings so cannot search to the end
std::reverse(str.begin(), str.begin() + first + 1);
...
ただし、文字列k = "ggggffffa"を指定すると、アルゴリズムが機能しないため、このアプローチには欠陥があります。この問題を正しく解決する方法がわかりません。それで、私はそれを自分で実装しようと試みることができるように理論的な解決策を求めています。
このアルゴリズムは問題を解決しますが、最適化が必要になる場合があります。
#include <iostream>
#include <string>
std::string foo(std::string* ss)
{
std::string res;
for (int i = 0; i < 3; i++)
for (int j = ss[i].size()-1; j >= 0; j--)
res.push_back(ss[i][j]);
return res;
}
int main()
{
std::string s = "ggggffffa";
std::string res = "";
for (unsigned int i = 1; i < s.size() - 1; i++)
for (unsigned int j = 0; j < i; j++)
{
std::string ss[3] = {s.substr(0, j+1), s.substr(j+1, i-j), s.substr(i+1)};
std::string r = foo(ss);
if (r < res || res == "") res = r;
}
std::cout << res << std::endl;
}
説明：
for (unsigned int i = 1; i < s.size() - 1; i++)
for (unsigned int j = 0; j < i; j++)
iで文字列を分割し、文字列jの配列に3つの部分文字列を書き込みます。std::string ss[3] = {s.substr(0, j+1), s.substr(j+1, i-j), s.substr(i+1)};
foo各部分文字列を逆にし、3つの部分を連結して、結果の文字列を返すすべての関数。if (r < res || res == "") res = r;
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加