build-a-string.rb

# https://www.hackerrank.com/contests/worldcodesprint/challenges/print-string

# Enter your code here. Read input from STDIN. Print output to STDOUT
require 'set'

t = gets.strip.to_i

class TestCase < Struct.new(:a, :b, :string); end

test_cases = []

t.times do
    n, a, b = gets.strip.split.map(&:to_i)
    string = gets.strip
    test_cases << TestCase.new(a, b, string)
end

def find_longest_common_substring(string, target)
    largest = 0
    (0...string.length).each do |starting_pos|
        length = 0
        i = starting_pos
        is_substring = true
        while i < string.length && length < target.length && is_substring
            if string[i] == target[length]
                length += 1
                i += 1
                if length > largest
                    largest = length
                end
            else
                is_substring = false
            end
        end
    end

    return "" if largest == 0

    target[0...largest]
end

def append(string, cost, test_case)
    char = test_case.string[string.length]
    [string + char, cost + test_case.a]
end

$total = 0

def copy(string, cost, test_case)
    rest = test_case.string[string.length..-1]
    before = Time.now
    largest = find_longest_common_substring(string, rest)
    now = Time.now
    difference = now - before
    $total += difference
    return nil if largest.empty?
    [string + largest, cost + test_case.b]
end

def pop(set)
    subset = set.take(1)
    set.subtract(subset)
    subset[0]
end

def minimum_cost(test_case)
    cheapest = Float::INFINITY
    
    choice = nil
    next_choice = ["", 0]
    
    while choice != next_choice
        choice = next_choice
        string, cost = choice
        if string == test_case.string
            cheapest = cost if cost < cheapest
        else
            appended = append(string, cost, test_case)
            copied = copy(string, cost, test_case)
            
            if copied
                is_worth_it = test_case.b < copied[0][string.length..-1].length * test_case.a
                if is_worth_it
                    next_choice = copied
                else
                    next_choice = appended
                end
            else
                next_choice = appended
            end
        end
    end
    
    cheapest
end

test_cases.each do |test_case|
    puts minimum_cost(test_case)
end