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

Question

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

stringalgorithmsubstringdynamic-programminglongest-substring

11

在一个长度为n的字符序列S中，每个字符可能会多次出现。你想要找到S的最长子序列，其中所有相同字符的出现都在同一个位置;

例如，如果S = aaaccaaaccbccbbbab，则最长的这样的子序列（答案）是aaaaaaccccbbbb，即= aaa__aaacc_ccbbb_b。

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

- pxm

有没有关于不同字符数量的限制？ - Ted Hopp

答案是aaaaaaccccbbbb，aaa__aaacc_ccbbb_b只是原始答案的解释。 - pxm

没有答案的限制，解决方案可以包含所有不同的字符，也可以只包含一个最长的字符。是子序列，所以必须保持顺序。 - pxm

3

请问以下表述是否正确？“在S中找到最少的位置，使得如果删除这些字符，剩余的序列具有以下特性：如果将其分解为相同字符的连续段，则没有两个连续段是由相同的字符组成的。” - Ted Hopp

是的，问题可以包含任意多个字符。基本上我们需要删除这些字符并获得最长的子序列，使得答案中所有出现的字符（如果包括在内）都出现在同一个位置。 - pxm

显示剩余3条评论

3个回答

0

编辑：这个解决方案对于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)。

- Ted Hopp

1

我认为如果字符的所有实例都必须在原始字符串中放在一起，那么这是一个很好的解决方案。但是，我认为这个问题有稍微不同的要求，即字符的所有实例必须在结果子序列中放在一起，但不一定在原始字符串中放在一起。对于给定的示例，您的算法会给出什么？我认为它会给出 aaaccbbb。 - Peter de Rivaz

1

@PeterdeRivaz - 好的，我花了一些时间重新阅读OP的要求。我现在想我理解了（在某种程度上）。我认为这个“解决方案”可能与实际问题无关。 - Ted Hopp

我得到了一个使用状态机来解决的提示，但我无法做到。 - pxm

-1

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)

- Lucas Brunialti

2

这段代码的作用是按字母顺序列出字符串中的所有字母。这样做的副作用是将相同的字符分组成块，但它忽略了一个事实，即如果包含特定字符的两个实例，则必须排除原始字符串中它们之间不同的每个字符。例如，对于输入ABA，它返回AAB而不是AA。 - j_random_hacker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- j_random_hacker · Accepted Answer

设计

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

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

长度为n的字符串的每个子序列要么是空字符串，要么是一个子序列，其第一个元素位于位置1 <= i <= n，并且后面跟着另一个子序列，该子序列位于从位置i + 1开始的后缀上。
如果我们逐个将字符（或更具体地说是字符位置）附加到子序列中，则为了构建满足有效性条件的所有子序列，每当我们添加一个字符c时，如果前一个添加的字符p与c不同，则不再可能在后面添加任何p字符。

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

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

递归函数应该接受两个参数：要处理的字符串和最近添加到子序列中的字符，该函数输出将附加到该字符上。第二个参数必须允许采用特殊值来指示尚未添加任何字符（这发生在顶级递归情况下）。一种实现此目标的方法是选择一个不出现在输入字符串中的字符，但这引入了不使用该字符的要求。明显的解决方法是传递第三个参数，一个布尔值，指示是否已经添加了任何字符。但是，只使用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秒！