arrays - 多模式匹配算法

Question

假设您有几种日期模式 P1 - Pn。

其中一些很简单，例如 P1 - 所有星期一，P2 - 所有星期二；其他更复杂，如 P4 - 所有工作日等。

对于自定义日期数组(V1、V2)，我必须创建最短的结果字符串，如图所示:

对于任何数组，我们必须创建代表数组中日期的字符串。最简单的方法是创建像 1.5.2013, 2.5.2013, 3.5.2013 ... 这样的字符串，但是结果字符串会很长。

使用几个预定义的模式，我们可以创建更短的结果字符串。

For result string I use following rules:

Single date format: DD.MM.YYYY (10 characters)
Enumeration (dates and patterns): comma and space (2 characters)
Interval of dates: DD.MM.YYYY-DD.MM.YYYY (21 characters)
Interval of pattern names: Px-Py (5 characters)
Special words: except (6 characters)

结果字符串示例:

• V1 使用 P4 模式:

  P4 except 01.05.2013-03.05.2013, 09.05.2013, 10.05.2013, 16.05.2013, 17.05.2013 (80 characters)

• V1 使用 Pn 模式:

  Pn 06.05.2013-08.05.2013, 13.05.2013-15.05.2013, 20.05.2013-24.05.2013, 27.05.2013-31.05.2013 (94 characters)

• V1 使用最佳模式匹配:

  P1-P3 01.05.2013-19.05.2013, P4 20.05.2013-31.05.2013 (54 characters)

主要目标是创建最短的结果字符串。据我了解，我们可以通过找到最佳匹配模式来实现这一目标。

目前我正在尝试适应背包问题和最长公共(public)子序列问题，但我不确定这是不是正确的方向。

如果有任何想法，我将不胜感激。

---

已更新

感谢 Jan Dvorak 对我的问题的额外简短描述:

目标是使用预定义的字典(P1..Pn 和所有间隔和单个日期)描述 V，其中允许交集、并集和减法，并且每个操作和原子都有预定义的成本(结果字符串中的字符数) ).

---

Answer 1

经过长时间的搜索，我们终于找到了非常接近我们想要的解决方案。

http://www.fpz.unizg.hr/traffic/index.php/PROMTT/article/view/1287

感谢大家的参与。