在一个长度为n的字符序列S中,每个字符可能会多次出现。你想要找到S的最长子序列,其中所有相同字符的出现都在同一个位置;
例如,如果S = aaaccaaaccbccbbbab,则最长的这样的子序列(答案)是aaaaaaccccbbbb,即= aaa__aaacc_ccbbb_b。
换句话说,在子序列中出现的任何字母字符只能出现在一个连续的块中。如果可能,给出一个多项式时间算法来确定解决方案。
在一个长度为n的字符序列S中,每个字符可能会多次出现。你想要找到S的最长子序列,其中所有相同字符的出现都在同一个位置;
例如,如果S = aaaccaaaccbccbbbab,则最长的这样的子序列(答案)是aaaaaaccccbbbb,即= aaa__aaacc_ccbbb_b。
换句话说,在子序列中出现的任何字母字符只能出现在一个连续的块中。如果可能,给出一个多项式时间算法来确定解决方案。
下面给出一个C++实现的动态规划算法,用于解决这个问题。运行时间的上界(可能不是紧的)由O(g*(n^2 + log(g)))给出,其中n是字符串的长度,g是输入中不同子序列的数量。我不知道如何很好地描述这个数字,但它可以像对于由n个不同字符组成的字符串一样糟糕,使得该算法在最坏情况下呈指数级时间复杂度。它还使用O(ng)空间来保存DP记忆化表。(与子字符串不同,子序列可以由原始字符串中的非连续字符组成。) 在实践中,只要不同字符的数量较小,算法就会很快。
提出这个算法的两个关键思想是:
管理上述第二点至少有两种方法。一种方法是维护一组不允许使用的字符(例如使用256位数组),我们随着向当前子序列添加字符而将其添加到其中。每次我们想要向当前子序列添加一个字符时,我们首先检查它是否被允许。
另一种方法是意识到每当我们必须禁止一个字符在后续子序列中出现时,我们可以通过从剩余的后缀中删除所有该字符的副本,并使用这个(可能更短的)字符串作为要递归解决的子问题来实现。这种策略的优点是使得求解器函数更有可能被调用多次以使用相同的字符串参数,这意味着在将递归转换为DP时可以避免更多的计算。这就是下面代码的工作原理。#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
calc()
实际上并不关心特定的字母,只关心它们的模式。例如,在将所有 A
替换为 Y
,所有 B
替换为 X
后,calc("YYYXX", true)
的结果与 calc("AAABB", true)
的结果相同。将字符串转换为规范形式(例如,第一个字母 => A
,下一个不同的字母 => B
等),然后再将结果转换回来,可以大大减少 calc()
所看到的不同字符串的数量,从而避免更多的工作和节省更多的内存。 - j_random_hacker编辑:这个解决方案对于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
、currentLength
、bestLength
转换为长度为m
的数组来轻松完成。最后,扫描bestLength
数组以查找最大条目的索引,并使用bestStart
数组中相应的条目作为答案。总复杂度为O(mn)。
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)
ABA
,它返回AAB
而不是AA
。 - j_random_hacker