时间戳

首页 > 解决方案 > 玻璃珠 - 后缀阵列如何应用在这里？

c++11 - 玻璃珠 - 后缀阵列如何应用在这里？

问题描述

此问题的问题陈述可在此链接中找到 - https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=660。当我第一次阅读这个问题时，我无法想象如何在这个问题中应用后缀数组概念。我从这个链接阅读了代码 - https://yuting-zhang.github.io/uva/2016/03/22/UVa-719.html。如果有人可以举一个小例子并帮助我完成应用后缀数组和 LCP 概念的完整跟踪，那将非常有帮助。

另外，我没有在我提到的链接中的代码中理解这一行的含义：

这个作业在做什么 - LCP[i + 1] == n - 1 - SA[i] ？

for (int i = 0; i < n; i++)
            if (SA[i] < (n >> 1)){
                if (i + 1 < n && SA[i + 1] < (n >> 1) && **LCP[i + 1] == n - 1 - SA[i]**) -- 
                    continue;
                printf("%d\n", SA[i] + 1);
                break;
            }

标签： c++11lexicographicsuffix-array

解决方案

让我们首先了解使用的概念：

  • 后缀数组：对于一个包含 n 个字符的字符串 s，s 的后缀数组保存了按字典顺序排序的 s 的 n+1 个可能的后缀。对于紧凑的表示，我们可以为每个后缀仅存储 s 中后缀的起始位置。

  • Longest-Common-Prefix Array：为后缀数组中的每两个连续对保存两个后缀的最长公共前缀的大小。

对于玻璃珠问题，我们得到一个表示圆形玻璃珠链的输入字符串。我们被要求找到“最薄弱的环节”，这意味着珠子的位置使得在该珠子之前切割链条并考虑从该珠子开始并围绕链条直到切割的绳子，是所有的字典中最小的可能的削减。当有多种可能的解决方案时，我们被要求返回输入字符串中最早出现的剪切。

考虑您提供的链接中的示例：

  • helloworld: 最薄弱的环节在第 10 位。这意味着我们之前就切断了d，产生了新的字符串dhelloworl。我们可以立即看到没有更好的位置可以剪切，因为d是出现在输入字符串中的最小字母。因此，没有其他剪切可以生成一个新的字符串，它在字典上小于我们以 开头的字符串d。我们看到，当字符串具有唯一的最小字符时，这个问题是微不足道的，例如d在这种情况下。

  • amandamanda: 最薄弱的环节在位置 11。这意味着我们在最后一个之前切断a，产生新的字符串aamandamand。再一次很明显，没有更好的剪切位置，因为没有其他剪切可以生成以 开头的字符串aa，因此没有其他剪切可以生成字典上小于 的字符串aamandamand。

  • dontcallmebfu: 最薄弱的环节在位置 6。这意味着我们在 之前切断a，产生新的字符串allmebfudontc。很明显，这是唯一可能的解决方案，因为a它是输入字符串中唯一的最小字符。

  • aaabaaa: 最薄弱的环节在位置 5。这意味着我们在a紧跟在之后的 之前切断b，产生新的字符串aaaaaab。我们可以看到这是最好的切割位置，因为它会在asb发生之前生成最长的可能序列。因此，在所有可能的切割生成的新字符串中，这个新字符串在字典上是最小的。

现在让我们考虑如何将 SA/LCP 应用于此问题：如您在第二个链接中所述，该方法是为双倍输入字符串构造 SA/LCP。将输入字符串加倍意味着连接输入字符串的两个副本。我们为什么要这样做？它使我们能够模拟玻璃珠链的圆形度。再次考虑示例helloworld（尺寸 10）。当我们将输入字符串加倍时，我们得到helloworldhelloworld. 当我们d在输入字符串中剪切之前，我们现在可以读取剪切生成的字符串，方法是从双倍字符串中的剪切向前​​移动 10 个字符helloworl|dhelloworl|d：

如果我们仔细看，我们会发现我们实际上从不需要第二个副本中的最后一个字符。达到第二个的唯一方法是d在第一个之后切割d。但是我们永远不会在第一个之后剪切d，因为这相当于在第一个副本的开头剪切。所以作为一个小的优化，我们可以省略第二个副本的最后一个字符，这是在你的第二个链接的代码中完成的，当用于创建第二个副本的循环只上升到n-1（n作为输入字符串的长度） ：

        for (int i = 0; i < n - 1; i++)
            st[i + n] = st[i];

在构造了加倍输入字符串的 SA 之后，按字典顺序最小的后缀应该在开头（因为 SA 按定义按字典顺序排序）。但是，我们必须记住 SA 还包含从双倍输入字符串的后半部分开始的后缀。但是这些对我们没有用，因为只有双倍输入字符串的前半部分中的剪切模拟了圆形珠链上的环绕，后面跟着第二个副本，而第二个副本后面什么都没有。

例如，考虑 的 SA helloworldhelloworl：

  • 19：（$空）
  • 9：dhelloworl$
  • 11:elloworl$
  • 1：elloworldhelloworl$
  • （......我省略了整个数组，因为我们只对开头感兴趣......）

我们可以看到字典上最小的项是空词$。但是这个切割对我们没有用，因为它发生在双倍输入字符串的后半部分。当我们将这个切割投影回输入字符串时，我们必须在最后一个珠子之后进行切割，或者等效地，在第一个珠子之前进行切割（因为玻璃珠链的圆形度）。因此，此切割生成的新字符串将是helloworld，它实际上在字典上并不小于 SA 中的第二个条目， dhelloworl。出于这个原因，我们必须跳过从双输入字符串的后半部分开始的 SA 条目。在您链接的代码中，此检查由

if (SA[i] < (n >> 1)){

wheren是原始字符串大小的两倍（第二个副本中省略最后一个字符的减一抵消了，因为我们将 插入$为终端字符）。是>> 1二进制左移一位，相当于除以二。因此，此检查确保仅考虑双倍字符串前半部分的剪切。

由于该问题具有额外的限制，即当存在多个解决方案时，应返回输入字符串中最早出现的解决方案，因此我们必须对 SA 条目应用额外的过滤。考虑第二个链接中的示例。我们有输入AAA并将其加倍（减一）到AAAAA. 后缀数组将是：

- 5: `$` (empty word)
- 4: `A$`
- 3: `AA$`
- 2: `AAA$`
- 1: `AAAA$`
- 0: `AAAAA$`

由于先前的检查，5、4、3 处的剪切被跳过，因为它发生在双倍输入字符串的后半部分。对于剩余的条目，2根据 SA，cut at 将是字典上最小的。但是，当将这些剪切投影回原始输入时，剪切 2、1、0 都会生成相同的字符串AAA。所以这三个cut在字典上都是等价的，其中0处的cut是最早的。因此 0 将是返回的正确答案。

因此，如果 SA 中的一个条目紧随其后，另一个条目会在原始珠链上生成相同的结果字符串，则我们必须跳过它。我们可以通过使用 LCP 数组来检查这一点，它告诉我们当前条目及其后继条目的公共前缀有多长。如果公共前缀的长度等于当前后缀的大小，则当前后缀完全包含在后继条目中。这是通过检查实现的

if (i + 1 < n && SA[i + 1] < (n >> 1) && LCP[i + 1] == n - 1 - SA[i])
  continue;

检查的各个部分意味着：

  • i+1 < n: 我们不是在 SA 的末尾，所以我们可以检查一个后继者。
  • SA[i + 1] < (n >> 1): 后继者不在双倍输入字符串的后半部分。
  • LCP[i + 1] == n - 1 - SA[i]: 回想一下，SA[i]给出了iSA 中第 th 后缀的起始位置。SA 是在双倍输入字符串上构建的，大小为n。因此n-1-SA[i]是后缀开头和字符串结尾之间的距离，因此是后缀的长度。如果你看AAA上面的例子，加倍的字符串将是AAAAA$（删除第二个副本中的 unreachable A，因为我们只对从前半部分开始并且长度最多为 3 的后缀感兴趣）。n将是2*3=6。后缀AAA$从位置 2 开始。然后n-1-2 = 3是后缀的长度（忽略$，对于所有后缀都相同）。所以支票上写着“ith suffix 等于 SA 中下一个后缀的最长公共前缀”。这意味着ith 后缀是下一个 SA 条目的前缀。因此，下一个 SA 条目表示输入字符串中较早出现的一个剪切，它产生一个字典上等效的新字符串。
  • continue表示跳过循环的当前迭代以继续循环的下一次迭代。即ith 后缀被跳过。

推荐阅读