优化“盖章”的方式。串成所需的字符串 [英] Optimal way to "stamp" string into desired string

问题描述

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

So, I was looking for an algorithm for the following problem:

为您提供了所需的字符串 s 和图章 t 。 t 也是一个字符串。令起始字符串为 len（s）*？ 。

You are given a desired string s, and a stamp t. t is also a string. Let the beginning string be len(s)*"?".

是否可以使用图章使用图章将起始字符串转换为字符串s？整个图章必须适合开头字符串（图章的边界不得超过????? ...字符串的边界）。

Is it possible to use the stamp to transform the beginning string into the string s using the stamp? The whole stamp must fit inside the beginning string (the stamp's borders may not exceed the ?????... string's borders).

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

Print the number of stamps required and print the left border of the stamp for each stamping.

示例：

AABCACA (desired result)

ABCA (stamp)

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

我的解决方法：
如果邮票的首字母不是所需字符串的首字母，则该任务无法完成。最后一个字母也是如此。如果戳记未在所需字符串中包含所有字母，则该任务是不可能的。

My solution: If the stamp's first letter is not the desired string's first letter, the task is not possible. The same goes for the last letter. If the stamp doesn't have all the letters in the desired string, the task is impossible.

我的算法如下：尝试在所需字符串中查找戳记。如果找到它，请将其删除并用问号替换。标记图章的左边框。

My algorithm goes like this: try to find the stamp in the desired string. If it is found, delete it and replace it with question marks. Mark down the left border of the stamp. Do this as long as you can.

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

Then look for the stamp's contiguous subarrays of size len(stamp)-1. If you find any of those, delete them and replace with question marks. Mark down the left border of the stamp.

然后寻找邮票的大小为len（stamp）-2的连续子阵列。如果发现其中任何一个，请将其删除并替换为问号。标记图章的左边框。这样做直到完成。

Then look for the stamp's contiguous subarrays of size len(stamp)-2. If you find any of those, delete them and replace with question marks. Mark down the left border of the stamp. Do that until you are finished. There you have the answer.

问题
我不确定我的代码有什么问题，因为它不能似乎通过了一些测试案例。

The problems I'm not sure what is wrong with my code as it can't seem to pass some test cases. There is probably a logical error.

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 = " ")

推荐答案

您描述的算法从根本上来说是有缺陷的。它产生的结果与图章实际上可以做的事情不符。例如，使用图章 AB 和字符串 AAA ，它会尝试在字符串的边界之外盖章以应用最终的 A 。它还将尝试使用邮票 ABC的 AB 和 BC 子字符串 code>紧挨着字符串 ABBC ，但是没有实际应用的邮票可以做到。

The algorithm you describe is fundamentally flawed. The results it produces simply don't correspond to things the stamp can actually do. For example, with stamp AB and string AAA, it will try to stamp beyond the borders of the string to apply the final A. It will also try to use use the AB and BC substrings of the stamp ABC directly next to each other for the string ABBC, but no actual application of the stamp can do that.

图章不能用于应用图章字符串的任意子字符串。它可以用于在以前的戳记应用程序上进行戳记，但是您的算法并未考虑过度标记的全部复杂性。另外，即使您可以标记图章字符串的任意子字符串，也没有证明算法会最小化图章应用程序。

The stamp cannot be used to apply arbitrary substrings of the stamp string. It can be used to stamp over previous stamp applications, but your algorithm doesn't consider the full complexity of overstamping. Also, even if you could stamp arbitrary substrings of the stamp string, you haven't proven your algorithm minimizes stamp applications.

这篇关于优化“盖章”的方式。串成所需的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！