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

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 的剩余部分重复出现；如果不是，return 0（基本情况）。当您爬回递归堆栈时，累积所有 1 计数，并且有您的值 k.

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

你能从那里拿走吗？

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

number of letters to be deleted from a string so that it is divisible by another string

algorithm

greedy