在有序列表中解决模糊的类别

Question

让我们以一个具体的例子来说明，希望我能讲得清楚。假设月份列表为（有序）：

一月<二月<三月<...< 十二月

（使用从零开始的整数表示月份），例如：

一月是0，二月是1，...，十二月是11。

现在假设我没有完整的月份名称，并且给出了以下列表，其中月份已缩写为它们的首字母，而“e”代表一个空类别，如下所示：

e，F，e，e，e

如果我建立了一个“明确的月份”列表（f: 1，s: 8，o: 9，n: 10，d: 11），我可以通过先计算第一个类别（使用减法和模12），然后从那里写出其他内容来填充空类别。然而，假设我收到以下列表：

e，A，e，e，J，e

然后我可以（直观地）计算，尽管“A”是模棱两可的（可能是四月或八月），但在这种情况下它只能是四月，因为八月在经过2个类别后没有任何“ J”跟随。找到这个后，我可以从头开始再次计算所有内容。

我的问题是：是否有此问题的分析解决方案（函数、算法），或者我的唯一希望是使用暴力来定义每个潜在关系？对于某些例子，无法编写消歧算法/函数：考虑一个由11个“ e”组成的“ J”，后跟一个由11个“ e”组成的“ J”……由于它们之间有一年，所以我无法将“ J”区分为1月、6月或7月。

答案: 我最终编写了Il-Bhima的答案，因为对于特定情况，正则表达式是可以接受的，即使运行时间较高O(mn)。然而，我接受Ben的答案作为正确答案，因为它涵盖了其他答案（提到了正则表达式解决方案），但也提出了更好的方法，即使用KMP算法O（m+n），尽管这是针对要匹配模式的字符串数量较大的情况。谢谢大家。

- Dervin Thunk

Answer 1

我不确定这是否正是您在寻找的内容，但您可以使用修改过的KMP字符串搜索算法来解决此问题。

修改的方法是将任何东西与空类别进行匹配。它甚至可以为您找到所有可能的值，比如您提到的带有11个e的J。

您还可以使用有限状态机来确定可能性，这就是正则表达式所做的事情。

- Ben S

---

谢谢，Ben。你能详细说明一下KMP算法如何找到我“J”的例子中的值吗？谢谢！ - Dervin Thunk

Answer 2

最简单的方法是使用正则表达式。假设您想匹配e, A, e, e, J, e。

构建以下正则表达式：r = ".A..J."

让c成为我们的控制字符串：

  c = "JFMAMJJASONDJFMAMJJASOND"

现在我们在字符串 c 中搜索所有与 r 匹配的内容，其中匹配的起始索引位于 c 的前一半。 通常来说，这可能不是最有效的方法。 最简单的解决方案是尝试将模式与控制字符串"JFMAMJJASOND"的每个循环移位进行匹配，其时间复杂度为O(nm)，其中n是模式的长度，m是控制字符串（在我们的例子中为JFMAMJJASOND）的长度。

- Il-Bhima

Answer 3

我们可以在Il-Bhima的答案基础上进一步解释一般情况。首先，我们认识到A、M或J中唯一真正模糊的一对是相隔六个月的两个J或相隔一年的两个相同字母。任何其他组合都将在控制字符串中产生一个明确的匹配（我建立了一张表来证明这一点）。

因此，您仅需要从整个起始列表中找出两个月份，它们之间的距离模12不为0或6。然后，您可以构建一个小型正则表达式与控制字符串进行匹配。或者，您可以构建一个查找表，其中包含有序对和月份之间的距离。

- Kristo