letters-benchmarking.rb

require 'fruity'

module Roland
  def self.letters(a, b)
    indexes = b.each_char.map do |letter|
      a.each_char.each_with_index.select {|l, _| l == letter }.map {|_, i| i }
    end

    start = indexes.shift

    if indexes.empty?
      [start]
    else
      start.product(*indexes).select {|x| x == x.sort }
    end
  end
end

module Tom
  def self.letters(a, b, starting_at = 0)
    if b.empty?
      [[]]
    else
      a.each_char.with_index.drop(starting_at).
        select { |c, _| c == b[0] }.map(&:last).
        flat_map { |i| letters(a, b[1..-1], i.succ).map(&[i].method(:+)) }
    end
  end
end

module Dominic
  def self.letters(haystack, needles)
    # base case: if the letters to match are empty, we've succeeded
    return [[]] if needles.empty?

    # base case: if the word to match in is empty, we've failed
    return false if haystack.empty?

    result = []

    if needles[0] == haystack[0]
      tail = letters(haystack[1..-1], needles[1..-1])
      result += tail.map { |t| [0] + t.map { |i| i + 1 } } if tail
    end

    tail = letters(haystack[1..-1], needles)
    result += tail.map { |t| t.map { |i| i + 1 } } if tail

    result
  end
end

module Dave
  extend self

  def letters(haystack_str, needle_str)
    haystack = haystack_str.chars
    needle   = needle_str.chars

    @pos_cache   = haystack.each.with_index.with_object(Hash.new { |h, k| h[k] = [] }) { |(c, i), h| h[c] << i if needle.include?(c) }
    @match_cache = Hash.new { |h, k| h[k] = {} }
    matches(needle)
  end

  def matches(chars, current_pos = -1)
    return [[]] unless chars.any?

    char, *rest = *chars
    @match_cache[char][current_pos] ||= begin
        this_matches = @pos_cache[char].select { |candidate_pos| candidate_pos > current_pos }
        this_matches.each_with_object([]) do |this_pos, memo|
        matches(rest, this_pos).each do |rest_matches|
          memo << [this_pos, *rest_matches]
        end
      end
    end
  end
end

module Peter
  extend self

  def letters(text, pattern)
    start = 0
    result = find_all_from_pattern(text, start, pattern)
  end

  def find_all_from_pattern(text, from, pattern)
    letter = pattern[0]
    remainder = pattern[1..-1]
    r = find_all_from_letter(text, from, letter)
    if remainder.size > 0
      r.each_with_object([]) do |previous, results|
        one_deeper = find_all_from_pattern(text, (previous+1), remainder)
        one_deeper.each do |deeper|
          results  << ([previous] + deeper)
        end
      end
    else # leaf node, end of iteration
      r
    end.map{ |e| Array(e) }
  end

  def find_all_from_letter(text, from, letter)
    [].tap do |result|
      while(match = find_one_from_letter(text, from, letter))
        result << match
        from = match + 1
      end
    end
  end

  def find_one_from_letter(text, from, letter)
    return nil unless letter
    index = text[from..-1].index(letter)
    index && (index + from)
  end
end

module Jason
  extend self

  def get_results(string, s_i, chars, c_i )
    finds = []
    while i = string.index(chars[c_i], s_i)
      if chars[c_i + 1]
        if more_finds = get_results(string, i + 1, chars , c_i + 1)
          finds += more_finds.map{|a| a.unshift(i)}
        else
          return nil
        end
      else
        finds << [i]
      end
      s_i = i + 1
    end
    return finds
  end

  def letters(a, b)
    return get_results(a, 0, b.split(//), 0 )
  end
end

haystack = "hello world" * 15
needle   = "lold"

contendors = [Roland, Dominic, Tom, Peter, Dave, Jason]
compare(contendors.each_with_object({}) { |c, h| h[c] = -> { c.letters(haystack, needle) } })

2.0.0 ~/scrap $ ruby letters-benchmarking.rb 
Running each test once. Test will take about 1 minute.
Dave is faster than Jason by 2x ± 0.1
Jason is faster than Peter by 2x ± 0.1
Peter is faster than Tom by 6x ± 0.1
Tom is faster than Roland by 60.00000000000001% ± 10.0%
Roland is faster than Dominic by 3x ± 0.1