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

Question

举个具体的例子，希望能说清楚。假设(有序的)月份列表:

January < February < March < ... < December

(代表月份的整数，从零开始)，使得

Jan is 0, Feb is 1, ..., Dec is 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 不明确(可能是四月或八月)，但在这种情况下它只能是四月，因为八月没有任何 J 在 2 个类别之后跟随它。一旦找到这个，我就可以再次从头开始计算所有内容。

最后，我的问题是:这个问题是否有解析解(函数、算法)，或者我唯一的希望是使用蛮力来定义每个潜在关系？对于某些示例，没有消歧算法/函数可以工作:考虑我有一个 J 后跟 11 个 e，再后跟一个 J 后跟 11 个 e ... 因为中间有一年，所以我不能将 J 歧义为一月、六月或七月。

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

Answer 1

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

修改将匹配空类别的任何内容。它甚至可以为您找到所有可能的值，例如您提到的带有 11 个 e 的 J。

你也可以使用 finite state machine确定可能性，这就是regular expression会做。