2

算法有一个问题。

问题如下：-

给你一个由字符 A、B、C、D 组成的蛋白质字符串。你必须在其中找到一个最小长度的序列。

例子

0 1 2 3 4 5 6 7 8 9 10 11 12
A B A C D C A B C D  C  C  D  

String to find is : BCD 

This string is find between (StartPoint, EndPoint)
1, 4
7, 9
1, 12
7, 12

Minimum length is of 7, 9.

So the answer is 7, 9

我的工作，

  1. 我们可以在 O(n^2) 中使用蛮力方法解决这个问题。
  2. 我们可以通过DP找到主字符串中出现的第一个序列，我的DP逻辑如下，
A = Main string
B = String to be find
DP = Dynamic programming function

n = A.size, m = B.size

Build an array of  DP[m+1][n+1]

DP[i][j], means If in A[0...i], B[0...j] is present or not.

This way we can find our first occurence of B in A. Now after this, I am stuck.

我需要你这边的一些提示。

请只给我提示/指导，不需要代码或实现。

4

2 回答 2

0

根据示例，我假设需要以与给定相同的顺序找到搜索字符串（即ACB不是有效的 find ABC）。

一般 DP 方法/提示：

我们试图最小化的函数是到目前为止的距离，所以这应该是存储在矩阵的每个单元格中的值。

对于字符串中的某个位置和搜索字符串中的某个位置，我们需要回溯到字符串中的所有先前位置，以便在搜索字符串中返回一个位置。对于所有这些，我们需要将距离添加到那里并记录最小值。

为了说明，假设搜索字符串为A, B, C, D. 那么ABC搜索字符串中的 for 和字符串中的位置，我们需要通过fori来查看位置。0i-1AB

给定一个 stringBACCD和一个 search string BCD，当查看两者的最后位置时，我们会得到类似的结果：

DP(BACCD, BCD) = min(4+DP(B, BC), 3+DP(BA, BC), 2+DP(BAC, BC), 1+DP(BACC, BC))

但是DP(B, BC)andDP(BA, BC)是无效的，因为BandBA不包含BC，更具体地说，不以 a 结尾C（因此可以为它们分配任意大的值）。

一旦我们到达搜索字符串中的最后一个字符，该值将表明我们找到了完整的搜索字符串，在字符串中的那个位置结束，因此它应该与全局最小值进行比较。

优化：

为了获得一个O(m*n)而不是O(m*n^2)运行时间，值得注意的是，您可以在看到另一个当前字母时立即停止向后迭代（因为，直到该点的任何序列都比只有最后一个字母向前移动的相同序列长） ， IE：

给定一个字符串ABCCD和一个搜索字符串ABC，当检查第二个时C，我们可以在到达第一个C（马上）时停止，因为ABC它比ABCC.

边注：

我认为一个可以比 DP 方法做得更好，但如果我在这里提出其他建议，它可能只是从Find length of minimum window that contains all characters in另一个字符串。

于 2013-10-07T13:31:12.080 回答
0

您的示例问题及其解决方案清楚地表明，解决方案将始终是一个数字对，其中包含子字符串的第一个字母的位置和子字符串的最后一个字母的位置，即

If the substring is BCD, then solution will be position of B, position of D

假设其余子字符串（在本例中为 C）位于解决方案对之间。

因此，为了给出提示，我们可以从找到子字符串的第一个字母在主字符串中的位置开始，并将这些位置存储在一个数组中。类似地，我们可以找到子字符串最后一个字母的位置并将它们存储在一个数组中。这将为我们提供一组可能的解决方案集，其中每一对将包含数组 1 中的一个数字和数组 2 中的一个数字，使得数组 2 中的数字大于数组 1 中的数字。现在我们可能最终会观察到有没有这样的对，这意味着没有解决方案，即主字符串中不存在子字符串，或者我们最终可能会找到一个或多个这样的对，这意味着可以有一个解决方案。现在剩下要做的就是找出解决方案对之间是否存在其余子字符串。如果最后发现不止一对这样的对，然后只是较高的数字减去较低的数字应该解决正确的解决方案。希望这会有所帮助，正如您所提到的，您不想知道整个答案，您只是在寻找提示:)

于 2013-10-07T13:05:10.417 回答