ハッシュ

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

class Hash
    M = 1046527

    def initialize
        @ary = []
    end

    def get_char(ch)
        if ch == 'A'
            return 1
        elsif ch == 'C'
            return 2
        elsif ch == 'G'
            return 3
        elsif ch == 'T'
            return 4
        end
        0
    end

    def get_key(str)
        sum = 0
        p = 1
        (0..(str.size - 1)).each do |i|
            sum += p * get_char(str[i])
            p *= 5
        end
        sum
    end

    def h1(key)
        key % M
    end

    def h2(key)
        1 + (key % (M - 1))
    end

    def h0(key, i)
        h1(key) + i * h2(key)
    end

    def exist?(str)
        key = get_key(str)
        i = 0
        while true do
            h = h0(key, i)
            if @ary[h] == str
                return true
            elsif @ary[h].nil?
                return false
            end
            i += 1
        end
    end

    def insert(str)
        key = get_key(str)
        i = 0
        while true do
            h = h0(key, i)
            if @ary[h] == str
                return false
            elsif @ary[h].nil?
                @ary[h] = str
                return true
            end
            i += 1
        end
    end
end
hash = Hash.new
n = gets.to_i
n.times do
    command, str = gets.split(" ")
    if command == 'insert'
        hash.insert(str)
    elsif command == 'find'
        if hash.exist?(str)
            puts "yes"
        else
            puts "no"
        end
    end
end