将字符串“标记”到所需字符串的最佳方式

Question

所以，我在寻找一个解决以下问题的算法：

您将得到一个所需的字符串s和一个图章t。t也是一个字符串。让起始字符串为len(s)*"?"。在

是否可以使用戳记将起始字符串转换为使用该戳记的字符串？整个图章必须放在起始字符串内（图章的边框不能超过？？？？？。。。字符串的边界）。在

打印所需的邮票数量，并为每个戳记打印邮票的左边框。在

示例：

AABCACA (desired result)

ABCA (stamp)

Solution:
3
1 4 2
explanation: ??????? → ABCA??? → ABCABCA → AABCACA.

我的解决方案： 如果戳记的第一个字母不是所需字符串的第一个字母，则无法执行该任务。最后一个字母也是如此。如果戳记没有包含所需字符串中的所有字母，则该任务是不可能的。在

我的算法是这样的：尝试在所需的字符串中找到标记。如果找到，请将其删除并用问号替换。把邮票的左边框划下来。尽你所能做这个。在

然后查找stamp的大小为len（stamp）-1的相邻子数组。如果您发现其中任何一个，请将其删除并替换为问号。把邮票的左边框划下来。在

然后查找stamp的连续子数组，大小为len（stamp）-2。如果您发现其中任何一个，请将其删除并替换为问号。把邮票的左边框划下来。一直做直到你完成。你知道答案了。在

问题 我不确定我的代码有什么问题，因为它似乎无法通过一些测试用例。可能有逻辑错误。在

^{pr2}$

Answer 1

你描述的算法根本上是有缺陷的。它产生的结果与邮票实际能做的事情并不相符。例如，使用stamp AB和字符串AAA，它将尝试在字符串边界之外进行标记，以应用最后的A。它还将尝试使用stamp ABC的AB和BC子字符串，直接相邻地使用字符串ABBC，但实际的stamp应用程序不能做到这一点。在

不能使用stamp应用stamp字符串的任意子字符串。它可以用于在以前的stamp应用程序上加戳，但是您的算法没有考虑到过大的复杂性。此外，即使您可以标记戳字符串的任意子字符串，也没有证明您的算法可以最小化标记应用程序。在

Answer 2

我们可以使用分而治之：让f(s)表示生成字符串s所需的最小戳记，其中“*”是通配符。然后：

• 吉利挑了一部分绳子，那是邮票最大的匹配。

• 将该部分设置为通配符，并将其左右各部分提供给f。

例如：

AABCACA (desired result)
ABCA (stamp)

f(AABCACA)
   ^^^^
   ABCA (match)

= 1 + f(A****) + f(****CA)

=> f(A****)
     ^^^^
     ABCA (match)

=> f(****CA)
       ^^^^
       ABCA

Total 3