n 文字のシーケンス S。各文字は、シーケンス内で何度も発生する可能性があります。同じ文字がすべて 1 か所にある S の最長部分列を見つけたいとします。
たとえば。S = aaaccaaaccbccbbbab の場合、そのような最長のサブシーケンス (回答) は aaaaaaccccbbbb ie= aaa__aaacc_ccbbb_b です。
言い換えれば、S に現れるアルファベット文字は、サブシーケンス内の 1 つの連続したブロックにしか現れない可能性があります。可能であれば、解を決定するための多項式時間アルゴリズムを与えてください。
以下に、この問題を解決する動的プログラミング アルゴリズムの C++ 実装を示します。実行時間の上限 (厳密ではない可能性があります) は、O(g*(n^2 + log(g))) で与えられます。ここで、n は文字列の長さ、g は文字列内の個別のサブシーケンスの数です。入力。この数値を特徴付ける良い方法はわかりませんが、n 個の異なる文字で構成される文字列の場合、O(2^n) と同じくらい悪い可能性があり、最悪の場合、このアルゴリズムは指数時間になります。また、DP メモ化テーブルを保持するために O(ng) スペースを使用します。(部分文字列とは異なり、部分文字列は、元の文字列の連続していない文字で構成されている場合があります。) 実際には、アルゴリズムは、個別の文字数が少ない場合は常に高速になります。
このアルゴリズムを考案する際に使用された 2 つの重要なアイデアは次のとおりです。
上記の 2 番目の点を管理するには、少なくとも 2 つの方法があります。1 つの方法は、現在のサブシーケンスに文字を追加するときに追加する、許可されていない文字のセットを維持することです (たとえば、256 ビット配列を使用)。現在のサブシーケンスに文字を追加するたびに、最初にそれが許可されているかどうかを確認します。
もう 1 つの方法は、文字がサブシーケンスの後半に出現することを許可しない必要があるときはいつでも、残りのサフィックスから文字のすべてのコピーを削除し、この (おそらく短い) 文字列をサブ問題として使用して解決することでこれを達成できることを認識することです。再帰的に。この戦略には、ソルバー関数が同じ文字列引数で複数回呼び出される可能性が高くなるという利点があります。つまり、再帰が DP に変換されるときに、より多くの計算を回避できます。これは、以下のコードがどのように機能するかです。
再帰関数は 2 つのパラメータを取る必要があります: 処理する文字列と、関数の出力が追加されるサブシーケンスに最後に追加された文字です。2 番目のパラメーターは、まだ文字が追加されていないことを示す特別な値を取ることができる必要があります (これは最上位の再帰ケースで発生します)。これを実現する 1 つの方法は、入力文字列に表示されない文字を選択することですが、これにより、その文字を使用しないという要件が導入されます。明らかな回避策は、文字が既に追加されているかどうかを示すブール値である 3 番目のパラメーターを渡すことです。ただし、2 つのパラメーターのみを使用する方が少し便利です。文字がまだ追加されているかどうかを示すブール値と、文字列です。ブール値が false の場合、その場合、文字列は単に処理対象の文字列です。true の場合、文字列の最初の文字が最後に追加された文字と見なされ、残りは処理対象の文字列になります。このアプローチを採用することは、関数が 2 つのパラメーターしかとらないことを意味し、メモ化を簡素化します。
上で述べたように、このアルゴリズムは最悪の場合指数時間です。これを完全に回避する方法は思いつきませんが、いくつかの最適化は特定のケースに役立ちます。私が実装した 1 つは、同じ文字の最大連続ブロックを 1 つのステップで常に追加することです。これは、そのようなブロックから少なくとも 1 文字を追加する場合、ブロック全体よりも少ない文字を追加することは決して最適ではないためです。これまでのところグローバルに最適な文字列を追跡し、現在の部分問題がより長い部分問題を生成できないと確信できる場合はいつでも再帰を短くするなど、他の分枝限定スタイルの最適化が可能です。これまでにサブシーケンスに追加された文字数と残りの文字の合計数は、これまでの最良のサブシーケンスの長さよりも短くなっています。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <map>
using namespace std;
class RunFinder {
string s;
map<string, string> memo[2]; // DP matrix
// If skip == false, compute the longest valid subsequence of t.
// Otherwise, compute the longest valid subsequence of the string
// consisting of t without its first character, taking that first character
// to be the last character of a preceding subsequence that we will be
// adding to.
string calc(string const& t, bool skip) {
map<string, string>::iterator m(memo[skip].find(t));
// Only calculate if we haven't already solved this case.
if (m == memo[skip].end()) {
// Try the empty subsequence. This is always valid.
string best;
// Try starting a subsequence whose leftmost position is one of
// the remaining characters. Instead of trying each character
// position separately, consider only contiguous blocks of identical
// characters, since if we choose one character from this block there
// is never any harm in choosing all of them.
for (string::const_iterator i = t.begin() + skip; i != t.end();) {
if (t.end() - i < best.size()) {
// We can't possibly find a longer string now.
break;
}
string::const_iterator next = find_if(i + 1, t.end(), bind1st(not_equal_to<char>(), *i));
// Just use next - 1 to cheaply give us an extra char at the start; this is safe
string u(next - 1, t.end());
u[0] = *i; // Record the previous char for the recursive call
if (skip && *i != t[0]) {
// We have added a new segment that is different from the
// previous segment. This means we can no longer use the
// character from the previous segment.
u.erase(remove(u.begin() + 1, u.end(), t[0]), u.end());
}
string v(i, next);
v += calc(u, true);
if (v.size() > best.size()) {
best = v;
}
i = next;
}
m = memo[skip].insert(make_pair(t, best)).first;
}
return (*m).second;
}
public:
RunFinder(string s) : s(s) {}
string calc() {
return calc(s, false);
}
};
int main(int argc, char **argv) {
RunFinder rf(argv[1]);
cout << rf.calc() << '\n';
return 0;
}
C:\runfinder>stopwatch runfinder aaaccaaaccbccbbbab
aaaaaaccccbbbb
stopwatch: Terminated. Elapsed time: 0ms
stopwatch: Process completed with exit code 0.
C:\runfinder>stopwatch runfinder abbaaasdbasdnfa,mnbmansdbfsbdnamsdnbfabbaaasdbasdnfa,mnbmansdbfsbdnamsdnbfabbaaasdbasdnfa,mnbmansdbfsbdnamsdnbfabbaaasdbasdnfa,mnbmansdbfsbdnamsdnbf
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,mnnsdbbbf
stopwatch: Terminated. Elapsed time: 609ms
stopwatch: Process completed with exit code 0.
C:\runfinder>stopwatch -v runfinder abcdefghijklmnopqrstuvwxyz123456abcdefghijklmnop
stopwatch: Command to be run: <runfinder abcdefghijklmnopqrstuvwxyz123456abcdefghijklmnop>.
stopwatch: Global memory situation before commencing: Used 2055507968 (49%) of 4128813056 virtual bytes, 1722564608 (80%) of 2145353728 physical bytes.
stopwatch: Process start time: 21/11/2012 02:53:14
abcdefghijklmnopqrstuvwxyz123456
stopwatch: Terminated. Elapsed time: 8062ms, CPU time: 7437ms, User time: 7328ms, Kernel time: 109ms, CPU usage: 92.25%, Page faults: 35473 (+35473), Peak working set size: 145440768, Peak VM usage: 145010688, Quota peak paged pool usage: 11596, Quota peak non paged pool usage: 1256
stopwatch: Process completed with exit code 0.
stopwatch: Process completion time: 21/11/2012 02:53:22
8 秒かかり、145Mb を使用した最後の実行は、多くの異なる文字を含む文字列で問題が発生する可能性があることを示しています。
編集:別の最適化に追加: サブシーケンスを開始する場所を探すループを終了するのは、これまでに発見された最高のものよりも優れている可能性がないことを証明できる場合です. これにより、最後の例に必要な時間が 32 秒から 8 秒に短縮されます!
編集:この解決策は、OPの問題には間違っています。他の人にとっては正しいかもしれないので、私はそれを削除しません。:)
関連する問題を考えてみましょう: 特定の文字が連続して出現する S の最長部分列を見つけます。これは線形時間で解決できます。
char c = . . .; // the given character
int start = -1;
int bestStart = -1;
int bestLength = 0;
int currentLength = 0;
for (int i = 0; i < S.length; ++i) {
if (S.charAt(i) == c) {
if (start == -1) {
start = i;
}
++currentLength;
} else {
if (currentLength > bestLength) {
bestStart = start;
bestLength = currentLength;
}
start = -1;
currentLength = 0;
}
}
if (bestStart >= 0) {
// longest sequence of c starts at bestStart
} else {
// character c does not occur in S
}
個別の文字 ( と呼ぶm) の数がかなり少ない場合は、このアルゴリズムを各文字に並行して適用するだけです。startこれは、、、、を長い配列bestStartに変換することで簡単に実行できます。最後に、配列をスキャンして最大のエントリのインデックスを探し、配列内の対応するエントリを答えとして使用します。全体の複雑さは O(mn) です。currentLengthbestLengthmbestLengthbestStart
import java.util.*;
public class LongestSubsequence {
/**
* @param args
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
execute(str);
}
static void execute(String str) {
int[] hash = new int[256];
String ans = "";
for (int i = 0; i < str.length(); i++) {
char temp = str.charAt(i);
hash[temp]++;
}
for (int i = 0; i < hash.length; i++) {
if (hash[i] != 0) {
for (int j = 0; j < hash[i]; j++)
ans += (char) i;
}
}
System.out.println(ans);
}
}
スペース: 256 -> O(256), このように言うのが正しいかどうかはわかりません..., O(256) は O(1) だと思います 時間: O(n)