什么是在Ruby中分割字符串以获取所有子字符串的最佳方法？

Question

例如，单词"stack"，我想获得一个类似的数组：

['s', 'st', 'sta', ... 'stack', 't', 'ta', ... , 'c', 'ck', 'k']

我通过以下代码实现了这个功能：

def split_word(str)
  result = []
  chas = str.split("")
  len = chas.size
  (0..len-1).each do |i|
    (i..len-1).each do |j|
      result.push(chas[i..j].join)
    end
  end
  result.uniq
end

有更好、更简洁的方法吗？谢谢。

- Jimmy Huang

---

一般建议：最好使用 map（函数式）而不是遵循“初始化空值+迭代+推送+返回”（命令式）模式。 - tokland

@tokland: 你所描述的不是一个映射（在Ruby中称为collect），而是一种折叠或更普遍的泛函递归（在Ruby中称为inject或reduce）。 - Jörg W Mittag

@Jörg，我所说的模式不是折叠（fold）：“a = []; [1,2,3].each { |x| a << 2x }; a”与“[1,2,3].map { |x| 2x }”相比。请看我的解决方案，这个问题可以用两个 map + 一个 flatten（concat）以纯函数式的方式解决。 - tokland

嗯，一张地图总是可以写成一个折叠……不管怎样，暂且不谈术语，我希望之前评论中的示例能够表达我的意图。根据 Haskell 的术语来说，这个问题是“a -> [a]”类型的，所以对我来说，使用 map 似乎是最自然的解决方案。 - tokland

@tokland：嗯，map只是fold的一种特殊情况 :-) 基本上，map f = foldr (λx y → f x : y) []。你在评论中提供的一般描述描述了fold的一般情况，但对于你所说的具体示例，当然是map。特别地，当init empty是与原始集合相同类型的集合，并且iterate只是应用转换函数，而push推送所有元素时，它就是一个map。实际上，fold是通用的：任何迭代（map、select、count等，甚至是each）都可以表示为fold。 - Jörg W Mittag

Answer 1

def split_word s
  (0..s.length).inject([]){|ai,i|
    (1..s.length - i).inject(ai){|aj,j|
      aj << s[i,j]
    }
  }.uniq
end

你还可以考虑使用 Set 替换数组用于结果。

另外，基于数组积的另一种想法：

def split_word s
  indices = (0...s.length).to_a
  indices.product(indices).reject{|i,j| i > j}.map{|i,j| s[i..j]}.uniq
end

- Mladen Jablanović

---

在用户@steel的建议下修正了第二个解决方案。 - Mladen Jablanović

输出应该是a、b、c、ab、bc、ac、abc。 - HarsHarI

Answer 2

我会写：

def split_word(s)
  0.upto(s.length - 1).flat_map do |start| 
    1.upto(s.length - start).map do |length| 
      s[start, length]
    end
  end.uniq
end

groups = split_word("stack")
# ["s", "st", "sta", "stac", "stack", "t", "ta", "tac", "tack", "a", "ac", "ack", "c", "ck", "k"]

使用map（函数式）通常比使用模式初始化空值+每个元素+追加+返回（命令式）更加清晰和紧凑。

- tokland

---

是的，tokland，你说得对。我也更喜欢函数式编程模式而不是命令式编程模式。谢谢你的建议！那么你认为哪种模式具有更好的性能呢？ - Jimmy Huang

@pake007：嗯，我说通常会更快，但是由于Ruby数组的扁平化和非惰性，我不太确定这里是否更快。无论如何，不要为性能而担心，差异可能很小。 - tokland

需要使用 flat_map 吗？如果需要，那么在哪些情况下需要使用 flat_map？我之所以问这个问题是因为用 map 替换 flat_map 会产生相同的结果。 - kraftydevil

@kraftydevil 如果没有使用 flat_map，你将得到一个嵌套的数组。列表推导式的规则是：在除最后一次迭代之外的所有迭代中都要使用 flat_map。 - tokland

Answer 3

def substrings(str)
  output = []
  (0...str.length).each do |i|
    (i...str.length).each do |j|
      output << str[i..j]
    end
  end
  output
end

这只是您的方法的简化版本，并且使用步骤更少 =)。

- user2566402

Answer 4

不太可能。

以下是我的翻译版本：

def split_word(str)
  length = str.length - 1
  [].tap do |result|
    0.upto(length) do |i|
      length.downto(i) do |j|
        substring = str[i..j]
        result << substring unless result.include?(substring)
      end
    end
  end
end

- changelog

Answer 5

def substrings(str)
  (0...str.length).map do |i|
     (i...str.length).each { |j| str[i..j]}
  end
end

这是另一种方法，对我来说更易读。

- Brent

Answer 6

这是获取所有可能子字符串的递归方式。

原始答案翻译成“最初的回答”。

def substrings str
  return [] if str.size < 1
  ((0..str.size-1).map do |pos|
    str[0..pos]
  end) + substrings(str[1..])
end

- Hrishi

Answer 7

迟来了，但这是我从重新格式化你的代码中得到的。

def substrings(string)
  siz = string.length
  answer = []

  (0..siz-1).each do |n|
    (n..siz-1).each do |i|
      answer << string[n..i]
    end
  end
  answer
end

- David Melin