0

假设我有一些包含序列的序列，{A,B}并且序列中的每个字母至少出现一次。如何在满足要求的序列中找到子字符串：

  • A 的数量与 B 的数量应该是可能的最高比率（#A/#B --> max）
  • 如果有许多具有相同比率的子字符串，我们必须返回最长的子字符串
  • 最后，如果有很多相同长度的，我们必须返回具有较低起始索引的那个

作为输出，我们想要找到的子字符串的开头索引及其长度。

例子

IN: AAABAA
OUT: index = 0, length = 6 (ratio is 5 : 1)
IN: BABAABBA
OUT: index = 1, length = 4 (ratio is 3 : 1)

任何提示如何解决问题？

作为一个请求，我正在添加我的想法：

  1. 如果某些两组连续的 A 与 3 个或更多 B 分开，则没有理由进一步测试它。这很简单，因为如果我们有像这样的子字符串：...A{k}BBBA{m}...ratio is (k+m):3while k:1or m:1must give better option

  2. 我还尝试按顺序查找 A 的所有最长子串。我认为我的序列很有可能是这样的，A{N1}BA{N2}BA{N3}但后来我发现它不一定是真的，例如：

    巴巴巴巴

我们可以看到有两个具有相同比率的序列：

  1. i=1 长度=4
  2. i=6 长度=4

但正如第 3 条规则所暗示的那样，我应该返回第一个，因为我说过我的算法是基于序列中最长的连续 A。

4

1 回答 1

1

这看起来像一个家庭作业，所以这可能不是一个要完全回答的好问题。然而，提示是从简单的案例开始：

  1. 如果B序列中只有一个会发生什么？
  2. 如果有两个 会发生什么B？假设您的序列包含x A's，然后是一个 's，然后是一个B' y As，然后是一个B，然后是z A's 并写一些不等式。
  3. 使推理适用于所有序列（提示：对于任何数字序列，a[1] ... a[n] (a[1] + ... + a[n])/n <= max(a[1], ... , a[n]只有当所有元素都相等时才会出现相等性）。
于 2013-10-19T15:46:01.733 回答