2

我根据这个答案为这个挑战写了一个解决方案。它成功地处理了给出的示例案例，但不是实际案例。

挑战：

给定两个字符串s，并且t,t是sif的子字符串，t作为连续的符号集合包含在s（因此，t必须不超过s）。

符号在字符串中的位置是在其左侧找到的符号总数，包括其自身（例如，“AUGCUUCAGAAAGGUCUUACG”中所有出现的 'U' 的位置是 2、5、6、15、17 和 18 ）。i位置处的符号s用 表示s[i]。

的子串s可以表示为s[j:k]，其中j和k表示子串在中的开始和结束位置s；例如，如果s = "AUGCUUCAGAAAGGUCUUACG"，那么s[2:5] = "UGCU"。

子串的位置s[j:k]是它的开始位置j；请注意，如果它作为子字符串出现不止一次，t则会有多个位置（请参阅下面的示例）。ss

鉴于：

两个 DNA 字符串s和t（每个长度最多 1 kbp）。

返回：

的所有位置t作为 的子字符串s。

样本数据集：

GATATATGCATATACTT
ATAT

样本输出：

2 4 10

对于示例，它有效。当然，您需要手动修剪格式，但这只是几秒钟的工作。

不接受实际数据和我生成的输出。

实际数据集：

CAAATAGTCACACAATAGTCGGCTAAATAGTCAATAGTCAAATAGTCAGAGCTAATAGTCTAAATAGTCGAAAAATAGTCATCAATAGTCTAAATAGTCAATAGTCGGAATAGTCAAAATAGTCAATAGTCAATAGTCAATAGTCGACTAAATAGTCCCAATAGTCTCAGAAATAGTCAATAGTCGTAATAGTCAATAGTCTAATAGTCTAATAGTCCAATAGTCTGTCAAATAGTCAATAGTCCAATAGTCGTTTAATAGTCCCCTTTACCAATAGTCAATAGTCCGAATAGTCAGGAATAGTCAGCACTAATAGTCAATAGTCCTAATAGTCCCAATAGTCAAAATAGTCAATAGTCTAAATAATAGTCCTAGCAGAAGAATAGTCTAATAGTCGGCAATAGTCAATAGTCAAATAGTCAGAATAGTCAAATAGTCGAAATAGTCAATAGTCAATAGTCAAATAGTCAAATAGTCAATAGTCAAATAGTCAAATAGTCAAATAGTCGAATAGTCTGTAATAGTCAATAGTCCTTCAATAGTCTAATAGTCATTCAATAGTCAAGAAATAGTCGGGGGAATAGTCCGAATAGTCAAATAGTCAATAGTCGAATAGTCTAATAGTCAATAGTCTAATAGTCTGATAATAGTCAAATAGTCAATAGTCTAAATAGTCGCCTATGCCAATAGTCTTATCAAATAGTCTCTTAATAGTCTAATAGTCAATAGTCAATAGTCTAATAGTCATAATAGTCAATAGTCAAGGAATAGTCCCATAATAGTCAATAGTCTTAATAGTCCAAACGAAATAGTCTTAATAGTCCCTAATAGTCACTAATAGTCGTAATAGTCATAATAGTCCAATAGTCTAAATAGTCTGCAATAGTCAAATAGTCAAATAGTCCGTACAATAGTCTTAATAGTCTTTGCGGCTCAATAGTCTCATAATAGTC
AATAGTCAA

实际输出（修整）：

26 33 93 109 118 125 132

代码：

def find_substring_locations(long, short)
  mpos = []
  re = Regexp.new(short)
  m = i = 0
  m = re.match( long, i ) { |k| j = k.begin(0); i = j + 1; mpos << j } while m
  return mpos
end

def plus_one(input)
  arr = []
  for i in input
    arr << (i += 1)
  end
  arr
end

main_string = gets.chomp
sub_string = gets.chomp
plus_one(find_substring_locations(main_string, sub_string))

我哪里做错了？它似乎有条不紊。

编辑： 原来问题是环境中的一个小问题。重启后问题无法重现。

4

2 回答 2

1

实际上不是答案，但您的代码按预期工作：

s = 'CAAATAGTCACACAATAGTCGGCTAAATAGTCAATAGTCAAATAGTCAGAGCTAATAGTCTAAA'\
    'TAGTCGAAAAATAGTCATCAATAGTCTAAATAGTCAATAGTCGGAATAGTCAAAATAGTCAATA'\
    'GTCAATAGTCAATAGTCGACTAAATAGTCCCAATAGTCTCAGAAATAGTCAATAGTCGTAATAG'\
    'TCAATAGTCTAATAGTCTAATAGTCCAATAGTCTGTCAAATAGTCAATAGTCCAATAGTCGTTT'\
    'AATAGTCCCCTTTACCAATAGTCAATAGTCCGAATAGTCAGGAATAGTCAGCACTAATAGTCAA'\
    'TAGTCCTAATAGTCCCAATAGTCAAAATAGTCAATAGTCTAAATAATAGTCCTAGCAGAAGAAT'\
    'AGTCTAATAGTCGGCAATAGTCAATAGTCAAATAGTCAGAATAGTCAAATAGTCGAAATAGTCA'\
    'ATAGTCAATAGTCAAATAGTCAAATAGTCAATAGTCAAATAGTCAAATAGTCAAATAGTCGAAT'\
    'AGTCTGTAATAGTCAATAGTCCTTCAATAGTCTAATAGTCATTCAATAGTCAAGAAATAGTCGG'\
    'GGGAATAGTCCGAATAGTCAAATAGTCAATAGTCGAATAGTCTAATAGTCAATAGTCTAATAGT'\
    'CTGATAATAGTCAAATAGTCAATAGTCTAAATAGTCGCCTATGCCAATAGTCTTATCAAATAGT'\
    'CTCTTAATAGTCTAATAGTCAATAGTCAATAGTCTAATAGTCATAATAGTCAATAGTCAAGGAA'\
    'TAGTCCCATAATAGTCAATAGTCTTAATAGTCCAAACGAAATAGTCTTAATAGTCCCTAATAGT'\
    'CACTAATAGTCGTAATAGTCATAATAGTCCAATAGTCTAAATAGTCTGCAATAGTCAAATAGTC'\
    'AAATAGTCCGTACAATAGTCTTAATAGTCTTTGCGGCTCAATAGTCTCATAATAGTC'

t = 'AATAGTCAA'

plus_one(find_substring_locations(s, t))
#=> [26, 33, 93, 109, 118, 125, 132, 172, 188, 231, 273, 312, 337, 346,
#    400, 407, 424, 441, 448, 455, 463, 471, 478, 486, 494, 520, 557,
#    589, 597, 620, 646, 654, 718, 725, 749, 756, 778, 882, 890]
于 2016-05-23T15:12:59.903 回答
1

我认为您的代码是正确的，除了一个错误。plus_one解决方案可以简化。

m = re.match( long, i ) { |k| j = k.begin(0); i = j + 1; mpos << j + 1} while m

但是有一种更简单的方法来实现。您不需要正则表达式，有一种更简单的方法来搜索子字符串匹配的索引：

String#index接受一个附加参数，即起始索引。

input = "CAAATAGTCACACAATAGTCGGCTAAATAGTCAATAGTCAAATAGTCAGAGCTAATAGTCTAAATAGTCGAAAAATAGTCATCAATAGTCTAAATAGTCAATAGTCGGAATAGTCAAAATAGTCAATAGTCAATAGTCAATAGTCGACTAAATAGTCCCAATAGTCTCAGAAATAGTCAATAGTCGTAATAGTCAATAGTCTAATAGTCTAATAGTCCAATAGTCTGTCAAATAGTCAATAGTCCAATAGTCGTTTAATAGTCCCCTTTACCAATAGTCAATAGTCCGAATAGTCAGGAATAGTCAGCACTAATAGTCAATAGTCCTAATAGTCCCAATAGTCAAAATAGTCAATAGTCTAAATAATAGTCCTAGCAGAAGAATAGTCTAATAGTCGGCAATAGTCAATAGTCAAATAGTCAGAATAGTCAAATAGTCGAAATAGTCAATAGTCAATAGTCAAATAGTCAAATAGTCAATAGTCAAATAGTCAAATAGTCAAATAGTCGAATAGTCTGTAATAGTCAATAGTCCTTCAATAGTCTAATAGTCATTCAATAGTCAAGAAATAGTCGGGGGAATAGTCCGAATAGTCAAATAGTCAATAGTCGAATAGTCTAATAGTCAATAGTCTAATAGTCTGATAATAGTCAAATAGTCAATAGTCTAAATAGTCGCCTATGCCAATAGTCTTATCAAATAGTCTCTTAATAGTCTAATAGTCAATAGTCAATAGTCTAATAGTCATAATAGTCAATAGTCAAGGAATAGTCCCATAATAGTCAATAGTCTTAATAGTCCAAACGAAATAGTCTTAATAGTCCCTAATAGTCACTAATAGTCGTAATAGTCATAATAGTCCAATAGTCTAAATAGTCTGCAATAGTCAAATAGTCAAATAGTCCGTACAATAGTCTTAATAGTCTTTGCGGCTCAATAGTCTCATAATAGTC"
query = "AATAGTCAA"

def substring_index(input, query)
  last = 0
  matches = []

  while index = input.index(query, last) do
    matches << index += 1
    last = index
  end
  matches
end


p substring_index(input, query)
# => [26, 33, 93, 109, 118, 125, 132, 172, 188, 231, 273, 312, 337, 346, 400, 407, 424, 441, 448, 455, 463, 471, 478, 486, 494, 520, 557, 589, 597, 620, 646, 654, 718, 725, 749, 756, 778, 882, 890]
于 2016-05-23T15:05:30.297 回答