如果我们有A长度为N的字符串B和长度为M的字符串,其中M <N,我可以快速计算我必须从字符串中删除的最小字母数,A以便字符串B不会作为子字符串出现A吗？
如果我们有微小的字符串长度,这个问题是很容易蛮力:您刚刚从迭代位掩码0来2^N看看B发生在这个序列的子字符串A.然而,当N可以达到10,000并且M可以达到1,000时,该算法显然会迅速崩溃.有更快的方法吗？
示例:A = ababaaB = aba.答案=.在A中1删除第二个a将导致abbaa,但不包含B.
编辑:用户nm发布了一个很好的反例:aabcc和abc.我们想要删除单个b,因为删除任何a或c将创建该字符串的另一个实例abc.