17

如果我们有A长度为 N 的字符串B和长度为 M 的字符串，其中 M < N，我可以快速计算必须从字符串中删除的最小字母数，A以便字符串B不会作为子字符串出现在A?

如果我们的字符串长度很小，这个问题很容易暴力破解：你只需从0to迭代一个位掩码2^N，看看是否B作为 . 的子序列中的子字符串出现A。但是，当 N 可以达到 10,000 并且 M 可以达到 1,000 时，这个算法显然很快就崩溃了。有没有更快的方法来做到这一点？

示例：A= ababaaB= aba。Answer= .删除 A1中的第二个a将导致abbaa，其中不包含B。

编辑：用户 nm 发布了一个很好的反例：aabcc和abc. 我们要删除单个b，因为删除任何a或c将创建另一个字符串实例abc。

4

5 回答 5

2

用动态规划解决它。令 dp[i][j] 成为使 A[0...i-1] 的后缀为 B[0...j-1] 的最小运算符，而 A[0...i] 则没有t 包含 B，dp[i][j] = Infinite要索引操作符是不可能的。然后

if(A[i-1]=B[i-1]) 
   dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])    
else dp[i][j]=dp[i-1][j]`,

return min(A[N][0],A[N][1],...,A[N][M-1]);`
于 2013-10-03T15:00:21.737 回答
0

查找主字符串中每个子字符串的索引。

然后使用动态编程算法（所以记住中间值），从主字符串中删除作为子字符串一部分的每个字母，将计数加 1，然后重复。

您可以找到这些字母，因为它们在每个匹配索引 + B 的长度的索引范围内。

A = ababaa
B = aba
count = 0

indeces = (0, 2)

A = babaa, aabaa, abbaa, abbaa, abaaa, ababa
B = aba
count = 1

(2nd abbaa is memoized)

indeces = (1), (1), (), (), (0), (0, 2)

answer = 1

您可以更进一步，并尝试记住子字符串的子字符串匹配索引，但这实际上可能不会提高性能。

不确定确切的界限，但在计算上不应该花费太长时间。

于 2013-10-12T06:27:34.103 回答
0

我不确定这个问题是否仍然有人感兴趣，但我有一个想法可能可行。

一旦我们决定问题不在于找到子字符串，而是决定从字符串 A 中删除哪个字母更方便，对我来说解决方案似乎很简单：如果您发现 B 字符串出现在 A 中，最好的办法是可以做的只是删除字符串内的一个字符，靠近右键……让我们说最后一个。这就是为什么如果你有一个实际上结束它的开始方式的子字符串，如果你在开头删除一个字符，你只删除一个 B 出现，而​​你实际上可以一次删除两个。

伪 cos 中的算法：

String A, B;
int occ_posit = 0;
N = B.length();

occ_posit = A.getOccurrencePosition(B); // pseudo function that get the first occurence of B into A and returns the offset (1° byte = 1), or 0 if no occurence present.

while (occ_posit > 0)  // while there are B into A
{
    if (B.firstchar == B.lastchar)  // if B starts as it ends
    {
        if (A.charat[occ_posit] == A.charat[occ_posit+1])
            A.remove[occ_posit - 1]; // no reason to remove A[occ_posit] here
        else
            A.remove[occ_posit]; // here we remove the last char, so we could remove 2 occurencies at the same time
    }
    else
    {
        int x = occ_posit + N - 1;
        while (A.charat[x + 1] == A.charat[x])
            x--; // find the first char different from the last one

        A.remove[x]; // B does not ends as it starts, so if there are  overlapping instances they overlap by more than one char. Removing the first that is not equal to the char following B instance, we kill both occurrencies at once.
    }
}

让我们用一个例子来解释：

A = "123456789000987654321" B = "890"

将此作为表格阅读：

occ_posit:  123456789012345678901

       A = "123456789000987654321"
       B =        "890"

第一次出现在 occ_posit = 8。B 在开始时没有结束，所以它进入第二个循环：

int x = 8 + 3 - 1 = 10;
while (A.charat[x + 1] == A.charat[x])
    x--; // find the first char different from the last one
A.remove[x];

while 发现 A.charat11 与 A.charat[10] (="0") 匹配，因此 x 变为 9，然后 while 退出，因为 A.charat[10] 与 A.charat9 不匹配。A 则变为：

A =“12345678000987654321”

没有更多的事件发生。

让我们尝试另一个： A = "abccccccccc" B = "abc"

第一次出现在 occ_posit = 1。B 开始时并没有结束，所以它进入第二个循环：

int x = 1 + 3 - 1 = 3;
while (A.charat[x + 1] == A.charat[x])
    x--; // find the first char different from the last one
A.remove[x];

while 发现 A.charat4 匹配 A.charat[3] (="c")，所以 x 变为 2，然后 while 退出，因为 A.charat[3] 不匹配 A.charat2。A 则变为：

A =“accccccccc”

让我们尝试重叠：

A = "abcdabcdabff" B = "abcdab"

该算法导致： A = "abcdacdabff" 不再出现。

最后，一个字母重叠：

A = “阿巴巴巴巴” B = “阿巴”

B 在它开始时结束，所以它进入第一个 if：

if (A.charat[occ_posit] == A.charat[occ_posit+1])
            A.remove[occ_posit - 1]; // no reason to remove A[occ_posit] here
        else
            A.remove[occ_posit]; // here we remove the last char, so we could remove 2 occurencies at the same time

这让 B 实例的最后一个“a”被删除。所以：

1° step: A= "abbbbabbabba" 2° step: A= "abbbbabbbba" 我们就完成了。

希望这可以帮助

编辑：请注意，当您的搜索接近 A 端时，必须稍微更正 algotirhm 以免出错，但这只是一个简单的编程问题。

于 2013-08-30T12:30:47.953 回答
0

这是我想出的草图。

首先，如果 A 包含 B 中未找到的任何符号，则将 A 拆分为一组仅包含 B 中找到的字符的较小字符串。将算法应用于每个较小的字符串，然后将它们粘在一起以获得总数结果。这确实起到了优化的作用。

接下来，检查 A 是否包含任何 B。如果没有，你就完成了。如果 A = B，则删除所有这些。

我认为一个相对贪婪的算法可能会起作用。

首先，标记 A 中属于至少一次 B 出现的所有符号。令 A = aabcbccabcaa，B = abc。粗体表示这些标记的字符：

abc bcc abc aa 。如果有重叠，标记所有可能的。这个操作是天真的近似（AB）操作，但我相信它可以在围绕（A / B）操作中完成。

考虑删除 A 中每个标记的字母：a abc bcc abc aa。

检查删除该标记字母是否减少了标记字母的数量。您只需要检查可能受删除字母影响的子字符串。如果 B 的长度为 4，则只有在检查 x 时才需要删除从以下位置开始的子字符串：

-------x------
    ^^^^

无论 x 是否存在，任何进一步的左或右都将存在。

例如：

在以下字符串中标记 [a]：a [a]bc bcc abc aa。

它的删除产生 abcbccabcaa，它在标记时产生abc bcc abc aa，它具有相同数量的标记字符。由于此操作只需要相对数量，因此对于每个选定的字母，它可以在大约 2B 时间内完成。对于每一个，分配两者之间的相对差异。选择一个最大的任意一个并将其删除。重复直到完成。每遍大概最多 2AB 次操作，最多 A 遍，总时间约为 2A^2 B。

在上面的示例中，分配了这些值：

aabcbccabcaa
 033   333

所以任意删除第一个标记的 b 给你：aacbccabcaa。如果你重复这个过程，你会得到：

aacbccabcaa
      333

最终结果完成。

我相信该算法是正确的最小化。我认为确实，只要 A 只需要一次删除，算法就必须是最优的。在这种情况下，减少最可能匹配（即：所有匹配）的字母应该是最好的。不过，我想不出这样的证据。我有兴趣找到任何最优性的反例。

于 2013-10-10T22:19:20.963 回答
0

你能对字符串进行图形搜索吗A？对于大 N 和特殊输入，这可能太慢了，但它应该比指数蛮力算法更好。也许是 BFS。

于 2013-03-10T02:55:46.930 回答