mangoicecream

matches.jl

str = "mangoicecream"
options = ["man", "ice", "cream", "go", "icecream", "mango"]

# prints the answer
function domatch(str, options, acc = [])
    for op in options
        cacc = copy(acc)
        if length(op) <= length(str) && str[1:length(op)] == op
            push!(cacc, op)
            if length(op) == length(str)
                println(join(cacc, " "))
            else
                domatch(str[length(op)+1:end], options, cacc)
            end
        end
    end
end

# returns the answer
function domatch2(str, options, acc = [])
    v = []
    for op in options
        cacc = copy(acc)
        if length(op) <= length(str) && str[1:length(op)] == op
            push!(cacc, op)
            if length(op) == length(str)
                push!(v, cacc)
            else
                push!(v, domatch2(str[length(op)+1:end], options, cacc))
            end
        end
    end
    v
end

# Same thing but with caching
d = Dict()
function domatchcached(str, options, acc = [])
    if haskey(d, str)
        return d[str]
    end
    v = []
    for op in options
        cacc = copy(acc)
        if length(op) <= length(str) && str[1:length(op)] == op
            push!(cacc, op)
            if length(op) == length(str)
                push!(v, cacc)
            else
                push!(v, domatch2(str[length(op)+1:end], options, cacc))
            end
        end
    end
    d[str] = v
    v
end