解析有序列表中的歧义类别
让我们举一个具体的例子，希望我能说清楚。假设(已排序的)月份列表：
一月<二月<三月<…<十二月
(整数表示月份，以零为基础)，这样
Jan是0，Feb是1，…，Dec是11。
现在假设我无法访问月份的全名，并得到以下列表，其中月份已缩短为第一个字母，e表示一个空类别，如下所示：
e，F，e，e，e
如果我构建了一个“明确的月份”列表(f:1，s:8，o:9，n:10，d:11)，我可以通过首先计算第一个类别(使用减法和mod 12)来填充空类别，然后从其中写出其余的内容。但是，假设我得到了这个列表
e，A，e，e，J，e
然后，我可以(直觉地)计算出，虽然A是模棱两可的(可能是4月或8月)，但在这种情况下，它只能是4月，因为在两个类别之后，8月没有任何_J_s跟随它。一旦我发现了这一点，我就可以从一开始就重新计算每件事。
最后，我的问题是:对于这个问题是否有一个解析解(函数、算法)，还是我唯一希望用蛮力来定义每个潜在关系？对于某些例子，任何消歧算法/函数都不起作用:假设我有一个J后面是11e，后面是一个J，然后是11e‘s。由于之间有一年的时间，我不能将J的歧义区分为一月、六月或七月。
running ：我最后编写了Il的答案，因为特别是在这个例子中，regex是可以的，即使在较高的运行时间O(mn)。然而，我接受Ben的答案是正确的，因为它包含其他的(提到regex解决方案)，但也建议使用KMP算法O(m+n)更好的方法，尽管这是针对更多的字符串来匹配模式。谢谢各位。
回答 2
Stack Overflow用户
发布于 2009-03-05 09:39:03
最简单的方法是使用正则表达式。假设您想要匹配e, A, e, e, J, e。
构造以下正则表达式：r = ".A..J."
让c成为我们的控制字符串：
c = "JFMAMJJASONDJFMAMJJASOND"现在，我们在字符串r中搜索c的所有匹配项，其中匹配的起始索引位于c的前半部分。
一般来说，这可能不是最有效的方法。最天真的解决方案是，尝试将模式与控制字符串"JFMAMJJASOND"的每一次循环移位相匹配，在O(nm) time中运行，其中n是模式的长度，m是控制字符串的长度(在我们的例子中是JFMAMJJASOND)。
Stack Overflow用户
发布于 2009-03-05 15:24:48
在一般情况下，我们可以以Il的回答为基础。首先，我们认识到，A，M或J的唯一真正的模棱两可的对是两个J，它们相隔6个月，或者是两个相同的字母，相隔一年。任何其他组合都将在控件字符串中产生明确的匹配。(为了证明这一点，我建立了一个由所有可能的组合组成的表格。)
因此，从整个开始列表中只需要两个月，其距离mod 12不是0或6，然后可以构建一个小的正则表达式来匹配控制字符串。或者，您可以构建一个查找表，其中包含有序对和月份之间的距离。
https://stackoverflow.com/questions/612321
复制相似问题
腾讯云开发者
