algorithm - 要从字符串中删除的字母数，以便它可以被另一个字符串整除

Question

我正在做这道题https://www.spoj.com/problems/DIVSTR/

给定两个字符串 S 和 T。 如果存在某个非负整数 k，则 S 可被字符串 T 整除，满足方程 S=k*T

要使 S 能被 T 整除，应从 S 中删除的最少字符数是多少？

主要思想是使用指针将 T 与 S 匹配，并在计数完成后计算 S 中出现的 T 实例的数量，将指针指向 T 的开头，如果不匹配，则比较 T 的第一个字母附上 S 现在的信件。

这段代码在他们提供的测试用例和我提供的自定义测试用例上工作得很好，但它无法通过隐藏的测试用例。

这是代码

def no_of_letters(string1,string2):
#     print(len(string1),len(string2))
    count = 0 
    pointer = 0
    if len(string1)<len(string2):
        return len(string1)
    if (len(string1)==len(string2)) and (string1!=string2):
        return len(string1)
    for j in range(len(string1)):
        if (string1[j]==string2[pointer]) and pointer<(len(string2)-1):
            pointer+=1
        elif (string1[j]==string2[pointer]) and pointer == (len(string2)-1):
            count+=1
            pointer=0
        elif (string1[j]!=string2[pointer]):
            if string1[j]==string2[0]:
                pointer=1
            else:
                pointer = 0
    return len(string1)-len(string2)*count

我认为应该混淆的一个地方是相同的字母可以是两个计数的一部分，但这应该不是问题，因为我们的答案不需要考虑重叠。

例如，S = 'akaka' T= 'aka' 将给出输出 2，无论考虑第一个 'aka',ka 作为计数还是第二个 ak,'aka'。

Answer 1

我相信解决方案比您制定的要简单得多。您只是想找出 T 的字符按顺序在 S 中出现了多少次。所有else 都是您删除的字符。例如，给定 RobertBaron 的 S="akbaabka" 和 T="aka" 示例，您可以编写例程来定位字符 a , k, a, 按此顺序，从 S 开始:

akbaabka
ak a^
# with some pointer, ptr, now at position 4, marked with a caret above

完成后，您现在可以对字符串的其余部分进行重复:

find_chars(S[ptr:], T)

每次调用时，您都会在S 中查找T；如果找到它，则计算 1 次重复并在 S 的剩余部分重复出现；如果不是，则返回 0(基本情况)。当您爬回递归堆栈时，累积所有 1 计数，这就是您的 k 值。

要删除的字符数量是len(s) - k*len(T)。

你能从那里拿走它吗？