https://www.theodinproject.com/lessons/ruby-sub-strings

ruby-sub-strings.rb

require 'set'

class Node
    attr_accessor :value, :parent

    def initialize(value = nil, parent = nil)
        @is_word = false
        @parent = parent
        @value = value
        @children = {}
    end

    def word
        s = ""
        node = self
        while node.value
            s += node.value
            node = node.parent
        end
        s.reverse
    end

    def is_word?
        @is_word
    end

    def mark_word
        @is_word = true
    end

    def child(char)
        if not @children.has_key?(char)
            @children[char] = Node.new(char, self)
        end
        @children[char]
    end

    def to_s indent = 0
        s = ""
        if @value
            s += ((" " * indent) + @value)
        end
        if @is_word
            s += " (word)"
        end
        @children.each do |key, value|
            s += "\n" + value.to_s(indent + 1)
        end
        s
    end
end

def build_trie(words)
    root = Node.new
    words.each do |word|
        node = root
        word.each_char { |char| node = node.child(char) }
        node.mark_word
    end
    root
end

def build_trie_from_file(file)
    root = Node.new
    File.open(file).each_line do |line|
        node = root
        line.strip.downcase.each_char { |char| node = node.child(char) }
        node.mark_word
    end
    root
end

def substrings(string, dictionary)
    root = build_trie(dictionary)
    nodes = []
    words = Set.new
    result = Hash.new { |h, k| h[k] = 0 }
    string.downcase.each_char do |char|
        if char == ' '
            words.each { |word| result[word] += 1 }
            words.clear
            next
        end

        nodes << root
        nodes.each_with_index do |node, i|
            nodes[i] = nodes[i].child(char)
            if nodes[i].is_word?
                words << nodes[i].word
            end
        end
    end

    words.each { |word| result[word] += 1 }

    result
end

dictionary = ["below","down","go","going","horn","how","howdy","it","i","low","own","part","partner","sit"]
puts substrings("below", dictionary)
puts substrings("Howdy partner, sit down! How's it going?", dictionary)