解决有序列表中的歧义类别

Question

让我们举一个具体的例子，希望我可以清楚。假设个月的（有序）列表：

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

（与站换了个整数，从零开始），这样

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

现在假设我没有访问个月的全名，和我给下面的列表，其中月已经缩短到他们的第一个字母，ē代表一个空的类别，是这样的：

E，F，E，E，E

如果我建立的 “明确个月” 的列表（F：1，S：8，O：9，N：10，d：11），我可以通过首先计算第一类（使用减法和mod 12）来填充空的类别，然后从那里写下其余的部分。然而，假设我给出的列表

E，A，E，E，J，E

然后，我可以（直觉）计算，虽然一个是模糊的（可能是四月或8月），在这种情况下，它只能是4月份，因为8月份之后没有任何两个类别之后的任何。一旦我发现这一点，我可以从一开始就再次计算一切。

我的问题最后是：有没有针对这个问题的分析解决方案（函数，算法），还是我唯一希望用暴力来定义每个潜在的关系？对于一些例子，没有歧义的算法/功能可以正常工作：考虑的情况下我有一个Ĵ其次是11 è的，随后Ĵ其次是11 è的......既然有是一年之间，我不能歧义地将J分解为1月，6月或7月。

回答：我最终编写了Il-Bhima的答案，因为在这种情况下，即使在较高的运行时间O（mn），正则表达式也可以。然而，我接受本的答案作为正确的答案，因为它包含了其他人（提到了正则表达式的解决方案），但也提出了使用KMP算法O（m + n）的更好方法，虽然这是针对更大数量的字符串以匹配模式。谢谢大家。

Answer 1

我不确定这是否正是您要找的内容，但您可以使用修改后的KMP string search algorithm来解决此问题。

该修改将匹配空白类别的任何内容。它甚至可以为你找到所有可能的价值，例如像你提到的那样的11 e。

你也可以使用一个finite state machine确定的可能性，这是一个多么regular expression会做。

Answer 2

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

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

让c是我们的控弦：

c = "JFMAMJJASONDJFMAMJJASOND" 

现在我们搜索的字符串c在r所有比赛，其中一场比赛的首发指数为内上半场c。

通常，这可能不是最有效的方法。最天真的解决方案，试图匹配模式与控制字符串的每个循环移位"JFMAMJJASOND"运行O(nm)时间，其中n是模式的长度，m是控制字符串的长度（在我们的情况下为JFMAMJJASOND）。

Answer 3

我们可以建立对IL-Bhima的回答一点的一般情况。首先，我们认识到，唯一真正模糊的A，M或J对是相隔六个月的两个J，或者相隔一年的两个相同的字母。任何其他组合都将在控制字符串中产生明确的匹配。 （我建的所有可能组合的一个表来证明这一点。）

因此，所有你需要您的整个首发名单的两个月，其距离国防部12不为0或6。然后，您可以建立一个小的正则表达式与控制字符串匹配。或者，您可以创建一个查找表，其中包含有序对和月份之间的距离。