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

让我们举一个具体的例子,希望我能清楚.假设(有序)月份列表:

1月<2月<3月<... <12月

(用整数代表几个月,零基础),这样

Jan是0,2月是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在2个类别之后跟随它.一旦我找到了这个,我可以从一开始就再次计算一切.

最后,我的问题是:是否存在针对此问题的分析解决方案(函数,算法),还是我唯一希望使用强力来定义每个潜在关系？对于一些例子,没有消歧算法/函数可以工作:考虑我有一个J后跟11 e的情况,然后是J后跟11 e ...因为有一年之间,我不能将J消除到1月,6月或7月的歧义.

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

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

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

您还可以使用有限状态机来确定可能性,这是正则表达式的作用.