3

给定一个后缀数组，来自 SRM 630 的 TopCoder 任务要求找到字符串中可以形成具有给定后缀数组的字符串的最小数量的不同字符。完整的问题陈述可以在 TopCoder 网站上找到。

我找到的最佳解决方案就在这里：https ://github.com/ftiasch/acm-icpc/blob/6db1ed02a727611830b974a1d4de38bab8f390f9/topcoder/single-round-match/single-round-match-630/SuffixArrayDiv1.java

这是ftiasch写的算法：

public int minimalCharacters(int[] array) {
    int n = array.length;
    int[] position = new int[n + 1];
    for (int i = 0; i < n; ++i) {
        position[array[i]] = i;
    }
    position[n] = -1;
    int[] minimum = new int[n + 1];
    for (int i = n - 1; i >= 0; --i) {
        minimum[i] = Integer.MAX_VALUE;
        for (int j = i + 1; j <= n; ++j) {
            boolean valid = true;
            for (int x = i; x < j; ++x) {
                for (int y = x + 1; y < j; ++y) {
                    valid &= position[array[x] + 1] < position[array[y] + 1];
                }
            }
            if (valid && minimum[j] < Integer.MAX_VALUE) {
                minimum[i] = Math.min(minimum[i], minimum[j] + 1);
            }
        }
    }
    return minimum[0];
}

我知道这是一种动态编程算法，但它是如何工作的？我真的需要一只手来理解它。

编辑

以下是 ftiasch 给我的回信：

嗨，爱丽儿，

首先感谢您的夸奖。坦率地说，我的解决方案并不是解决问题的最佳方案。最佳的运行时间为 O(n)，但我的运行时间为 O(n^4)。我只是在比赛中选择了这个想法，因为 n 相对较小。

请记住，相同的字符在 SA 中变得连续。由于问题要求字符数最少，所以我决定使用动态编程将 SA 划分为连续的段，以便每个段以相同的字符开头。

假设 i < j，S[SA[i]] == S[SA[j]] 的必要条件是什么？字典比较表明 suffix(SA[i] + 1) 应该小于 suffix(SA[j] + 1)。我们不难发现，条件也是充分的。

如果您有任何其他问题，请写信给我。:)

编辑1

感谢大卫，我们终于成功了。这是来自 David 的 Python 版本的 java 中的线性时间算法：

public int minimalCharacters(int[] array) {
    int n = array.length, i;
    if (n == 0)
        return 0;
    int[] array1 = new int[n + 1];
    for (i = 0; i < n; i++)
        array1[1 + i] = array[i];
    int[] position = new int[n + 1];
    for (i = 0; i < n + 1; i++)
        position[array1[i]] = i;
    int k = 1;
    for (i = n; i > 1; i--) {
        if (position[array1[i] + 1] <= position[array1[i - 1] + 1])
            k++;
    }
    return k;
}
4

1 回答 1

4

这是一个二次时间算法。后缀数组为每对后缀指定它们如何按字典顺序进行比较（并且空后缀总是小于所有后缀）。让我们s成为未知字符串，并假设我们正在比较 suffixs[i...]和 suffix s[j...]。如果s[i] != s[j]，则比较s[i]和s[j]解决它。否则，结果与我们比较s[i+1...]和 相同s[j+1...]。

假设我们希望确保s[i...] < s[j...]。显然我们需要 s[i] <= s[j]. 事实上，除非s[i+1...] < s[j+1...]，我们需要严格的不等式s[i] < s[j]，否则决胜局会走错路。否则，s[i] == s[j]无论字符串的其余部分如何，都足够了。将所有不等式收集为有向图中的弧，其中顶点对应于 中的位置s。该图必然是按后缀的总顺序非循环的。如果不等式是严格的，则使每个弧长为 1，否则为长度 0。输出最长路径的长度，加一（如果图为空，则为零）。

通过相应的不等式链，至少需要这么多不同的字母。可能不太清楚的是，这么多不同的字母就足够了，但是如果我们s通过从那里开始的最长路径的长度来确定每个顶点/位置的标签，那么每个弧的头部和尾部都会被适当地标记。

为了得到线性时间，我们可以利用图的结构。很简单（虽然不是微不足道的；该图毕竟是度量的）表明访问图的所有顶点的路径是最长的，所以我们只需要计算它的长度。

下面是示例代码的音译版本minChars1（导入迭代工具minChars2minChars3minChars4

def minChars1(array):
    n = len(array)
    position = [-1] * (n + 1)
    for i in range(n):
        position[array[i]] = i
    infinity = n + 1
    minimum = [infinity] * (n + 1)
    minimum[n] = 0
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n + 1):
            valid = True
            for x in range(i, j):
                for y in range(x + 1, j):
                    valid = valid and position[array[x] + 1] < position[array[y] + 1]
            if valid and minimum[j] < infinity:
                minimum[i] = min(minimum[i], minimum[j] + 1)
    return minimum[0]


def lengthOfLongestPath(graph, memo, i):
    if i not in memo:
        result = 0
        for w, j in graph[i]:
            result = max(result, w + lengthOfLongestPath(graph, memo, j))
        memo[i] = result
    return memo[i]


def minChars2(array):
    n = len(array)
    position = [-1] * (n + 1)
    for i in range(n):
        position[array[i]] = i
    graph = {}
    for i in range(n):
        graph[i] = []
        for j in range(n):
            if position[i] > position[j]:
                w = 0 if position[i + 1] > position[j + 1] else 1
                graph[i].append((w, j))
    memo = {None: -1}
    for i in range(n):
        lengthOfLongestPath(graph, memo, i)
    return max(memo.values()) + 1


def minChars3(array):
    n = len(array)
    position = [None] * n
    for i in range(n):
        position[array[i]] = i
    for k in range(n):
        for s in itertools.product(range(k), repeat=n):
            valid = True
            for i in range(n):
                for j in range(n):
                    valid = valid and (s[i:] < s[j:]) == (position[i] < position[j])
            if valid:
                return k
    return n


def minChars4(array):
    n = len(array)
    if n == 0:
        return 0
    array1 = [n] * (n + 1)
    for i in range(n):
        array1[1 + i] = array[i]
    position = [None] * (n + 1)
    for i in range(n + 1):
        position[array1[i]] = i
    k = 1
    for i in range(n, 1, -1):
        if position[array1[i] + 1] <= position[array1[i - 1] + 1]:
            k += 1
    return k


def test():
    for n in range(7):
        for array in itertools.permutations(range(n)):
            assert minChars1(array) == minChars2(array) == minChars3(array) == minChars4(array)


test()
于 2014-09-05T01:27:24.210 回答