带约束的最优字符串分割

Question

问题陈述：

您将获得一个长字符串（S）和一个禁止子字符串列表（F）。目标是将 ( S ) 划分为尽可能少的非空段，使得：

1. 列表 ( F ) 中没有段包含任何禁止子字符串。
2. 段总数最小化。
3. 各段之间的长度差异尽可能小 — 换句话说，各段的大小应彼此接近。
4. 如果无法实现有效分割，输出一条指示失败的消息。
5. 考虑 ( S ) 具有重复模式或包含每个禁止子字符串的情况。

示例：

• 输入： ( S = "abcdeabc" ), ( F = ["bc", "de", "abcd"] )
• 输出： 诸如 (["a", "bcd", "eabc"]) 之类的分段将是无效的，因为它包含禁止的子字符串。如果满足所有条件，最小的有效分段可能是 (["abc", "deabc"])。

Answer 1

段的数量由包含禁止字符串的区域的数量决定。 如果禁止的字符串没有重叠，那么您只需切割每个禁止的字符串，调整切割以使段长度尽可能接近。

当禁止的字符串重叠时就会出现问题。 想象一下：

S = "abcdefa"
F = "bcd", "cde", "def"

现在所有 3 个禁止字符串都存在，但是有一个禁止字符串区域，即“bcdef”，无法通过一次切割来分割。输出可能是：“abc”、“de”、“fa”

所以算法一定是：

1. 查找禁止字符串的区域。
2. 确定每个区域所需的最小切割次数
3. 调整切割位置以使段长度最佳匹配（假设约束 2 优先于 3）