最长的子序列,在1个位置出现所有字符

Question

在n个字符的序列S中; 每个字符可能在序列中出现多次.你想找到S的最长子序列,其中所有出现的相同字符都在一个地方;

对于前者 如果S = aaaccaaaccbccbbbab,那么最长的这样的子序列(答案)是aaaaaaccccbbbb ie = aaa__aaacc_ccbbbb.

换句话说,S中出现的任何字母字符可能只出现在子序列中的一个连续块中.如果可能,给出一个多项式时间算法来确定解.

Answer 1

设计

下面我给出了解决这个问题的动态规划算法的C++实现。运行时间的上限（可能并不严格）由 O(g*(n^2 + log(g))) 给出，其中 n 是字符串的长度，g是输入。我不知道描述这个数字的好方法，但对于由 n 个不同字符组成的字符串来说，它可能会像 O(2^n) 一样糟糕，使得该算法在最坏的情况下呈指数时间。它还使用 O(ng) 空间来保存 DP 记忆表。（与子字符串不同，子序列可能由原始字符串中不连续的字符组成。）实际上，只要不同字符的数量很少，该算法就会很快。

提出该算法的两个关键思想是：

• 长度为 n 的字符串的每个子序列要么是 (a) 空字符串，要么是 (b) 第一个元素位于某个位置 1 <= i <= n 的子序列，并且后跟从位置 i 开始的后缀上的另一个子序列+1。
• 如果我们一次将一个字符（或更具体的字符位置）附加到子序列中，那么为了构建所有且仅满足有效性标准的子序列，每当我们添加字符 c 时，如果前一个字符添加了 p，与c不同，那么以后就不能再添加任何p字符了。

至少有两种方法可以解决上述第二点。一种方法是维护一组不允许的字符（例如使用 256 位数组），当我们向当前子序列添加字符时，我们也将其添加到其中。每次我们想要向当前子序列添加一个字符时，我们首先检查是否允许。

另一种方法是认识到，每当我们必须禁止某个字符稍后出现在子序列中时，我们可以通过简单地从剩余后缀中删除该字符的所有副本，并使用这个（可能更短）字符串作为要解决的子问题来实现这一点递归地。这种策略的优点是使得求解器函数更有可能使用相同的字符串参数被多次调用，这意味着当递归转换为 DP 时可以避免更多的计算。这就是下面的代码的工作原理。

递归函数应该采用 2 个参数：要处理的字符串，以及最近附加到函数输出将附加到的子序列的字符。必须允许第二个参数采用特殊值，以指示尚未附加任何字符（这发生在顶级递归情况下）。实现此目的的一种方法是选择一个未出现在输入字符串中的字符，但这引入了不使用该字符的要求。明显的解决方法是传递第三个参数，这是一个布尔值，指示是否已添加任何字符。但仅使用 2 个参数会稍微方便一些：一个布尔值（指示是否已添加任何字符）和一个字符串。如果布尔值为 false，则该字符串只是要处理的字符串。如果为 true，则字符串的第一个字符将被视为最后添加的字符，其余字符就是要处理的字符串。采用这种方法意味着该函数仅需要 2 个参数，从而简化了记忆。

正如我在顶部所说，该算法在最坏的情况下是指数时间的。我想不出一种方法来完全避免这种情况，但一些优化可以帮助某些情况。我实现的一种方法是始终在一步中添加相同字符的最大连续块，因为如果您从这样的块中添加至少一个字符，那么添加少于整个块的字符永远不会是最佳选择。其他分支定界式优化也是可能的，例如跟踪迄今为止的全局最佳字符串，并在我们可以确定当前子问题无法产生更长的子问题时缩短递归 - 例如，当字符数减少时到目前为止添加到子序列中的字符加上剩余的字符总数小于迄今为止最佳子序列的长度。

代码

#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 秒！