python - 将 "stamp"字符串转换为所需字符串的最佳方法

Question

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

给你一个想要的字符串s，和一个标记t。 t 也是一个字符串。让起始字符串为 len(s)*"?"。

是否可以使用戳记将开始的字符串转换为使用戳记的字符串s？整个图章必须适合开头的字符串(图章的边界不能超过 ??????... 字符串的边界)。

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

示例:

AABCACA (desired result)

ABCA (stamp)

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

我的解决方案:如果邮票的第一个字母不是所需字符串的第一个字母，则无法完成任务。最后一封信也是如此。如果图章不包含所需字符串中的所有字母，则无法完成任务。

我的算法是这样的:尝试在所需的字符串中找到戳记。如果找到，将其删除并替换为问号。标记邮票的左边框。尽可能长时间地这样做。

然后寻找 stamp 的大小为 len(stamp)-1 的连续子数组。如果您找到其中任何一个，请将其删除并替换为问号。标记邮票的左边框。

然后寻找 stamp 的大小为 len(stamp)-2 的连续子数组。如果您找到其中任何一个，请将其删除并替换为问号。标记邮票的左边框。这样做直到你完成。这就是答案。

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

import sys

desiredString = input()
stamp = input()
stampingSpots = []

if (len(set(desiredString)) != len(set(stamp)) or stamp[0] != desiredString[0] or stamp[-1] != desiredString[-1]):
    print("-1")
    sys.exit()


def searchAndReplace(stringToFind, fix): #Search for stringToFind and replace it with len(stringToFind)*"?". Fix is used to fix the position.
    global desiredString
    for x in range(0, len(desiredString)-len(stringToFind)+1):
        if desiredString[x:x+len(stringToFind)] == stringToFind:
            stampingSpots.append(x+1-fix) #Mark down the stamping spot
            firstPart = desiredString[:x]
            firstPart += len(stringToFind)*"?"
            firstPart += desiredString[len(firstPart):]
            desiredString = firstPart
            return True
    return False

while(searchAndReplace(stamp,0)): #Search for the full stamp in desiredString
    searchAndReplace(stamp,0)



length = len(stamp)-1
while(length > 0):
    for firstPart in range(0, len(stamp)-length+1):
        secondPart = firstPart+length
        while(searchAndReplace(stamp[firstPart:secondPart], firstPart)):
            searchAndReplace(stamp[firstPart:secondPart], firstPart)

    if len(stampingSpots) > 10*len(desiredString): #Too much output, not possible
        print("-1")
        sys.exit()
    length -= 1


print(len(stampingSpots))    
for i in reversed(stampingSpots):
    print(i, end = " ")

Answer 1

您描述的算法存在根本性缺陷。它产生的结果根本不符合印章实际可以做的事情。例如，带有邮票 AB和字符串 AAA , 它会尝试在字符串的边界之外加戳以应用最后的 A .它还将尝试使用 AB和 BC邮票的子串 ABC直接相邻的字符串 ABBC ，但邮票的实际应用无法做到这一点。

戳记不能用于应用戳记字符串的任意子字符串。它可用于标记以前的标记应用程序，但您的算法没有考虑覆盖标记的全部复杂性。此外，即使您可以标记标记字符串的任意子字符串，您也没有证明您的算法可以最大限度地减少标记应用。