# Ruby 1.8에서테스트
def min(i, j)
return (i <= j) ? i : j
end
# str_1, str_2에서 공통되는 부분문자열의 길이를 리턴해준다
def comm_len(str_1, str_2)
len = 0
(min(str_1.length, str_2.length)).times do |i|
(str_1[i] == str_2[i]) ? (len += 1) : break
end
return len
end
# str에 있는 문자열을 앞에서부터 차례대로 접미사 배열을 만듬
# banana였으면 a[0] = banana, a[1] = anana,이렇게 해서 a[5] = a 가 됨
def get_suffix_arr(str, len)
suffix_arr = Array.new(len)
suffix_arr.each_index {|i| suffix_arr[i] = str.slice(i ... len)}
return suffix_arr
end
# 중복된 문자열중에 가장 긴 부분문자열을 찾는것임
# programming pearls ch 15에 2번째에 나오는 문제이다.
def longest_dup_substr(str)
longest_idx, max_len = 0, 0
str_len = str.length
# 공통된 문자열이 중복되서 나왔으면 두개의 다른 접미사로
# 들어가 있을것임 같은 접미사들이 모이도록 하기위해 접미사배열을 만들어 정렬을함
# 그럼 그 놈들 중에 겹치는 놈들을 찾아 그 길이가 제일 긴놈이
# 제일긴 중복된 문자열이다
suffix_arr = get_suffix_arr(str, str_len).sort!
# 접미사 배열이 정렬되갖구있으니, 인접한 문자열끼리 계속 공통부분의 길이를 찾아나감
(str_len - 1).times do |i|
ret = comm_len(suffix_arr[i], suffix_arr[i + 1])
if ret > max_len
max_len = ret
longest_idx = i
end
end
# 가장 긴 공통 문자열이 있는 index에서 있는 문자열을 max_len만큼 잘라서 리턴
return suffix_arr[longest_idx].slice(0 ... max_len).strip
end
require 'test/unit'
class TestLoneestDupSubstr < Test::Unit::TestCase
def test_method
ans = ["ana", "can do for you"]
input = ["banana&grape",
"""Ask not what your country can do for you,
but what you can do for your country""" ]
input.each_index {|i| assert_equal(ans[i], longest_dup_substr(input[i]))}
end
end
return (i <= j) ? i : j
end
# str_1, str_2에서 공통되는 부분문자열의 길이를 리턴해준다
def comm_len(str_1, str_2)
len = 0
(min(str_1.length, str_2.length)).times do |i|
(str_1[i] == str_2[i]) ? (len += 1) : break
end
return len
end
# str에 있는 문자열을 앞에서부터 차례대로 접미사 배열을 만듬
# banana였으면 a[0] = banana, a[1] = anana,이렇게 해서 a[5] = a 가 됨
def get_suffix_arr(str, len)
suffix_arr = Array.new(len)
suffix_arr.each_index {|i| suffix_arr[i] = str.slice(i ... len)}
return suffix_arr
end
# 중복된 문자열중에 가장 긴 부분문자열을 찾는것임
# programming pearls ch 15에 2번째에 나오는 문제이다.
def longest_dup_substr(str)
longest_idx, max_len = 0, 0
str_len = str.length
# 공통된 문자열이 중복되서 나왔으면 두개의 다른 접미사로
# 들어가 있을것임 같은 접미사들이 모이도록 하기위해 접미사배열을 만들어 정렬을함
# 그럼 그 놈들 중에 겹치는 놈들을 찾아 그 길이가 제일 긴놈이
# 제일긴 중복된 문자열이다
suffix_arr = get_suffix_arr(str, str_len).sort!
# 접미사 배열이 정렬되갖구있으니, 인접한 문자열끼리 계속 공통부분의 길이를 찾아나감
(str_len - 1).times do |i|
ret = comm_len(suffix_arr[i], suffix_arr[i + 1])
if ret > max_len
max_len = ret
longest_idx = i
end
end
# 가장 긴 공통 문자열이 있는 index에서 있는 문자열을 max_len만큼 잘라서 리턴
return suffix_arr[longest_idx].slice(0 ... max_len).strip
end
require 'test/unit'
class TestLoneestDupSubstr < Test::Unit::TestCase
def test_method
ans = ["ana", "can do for you"]
input = ["banana&grape",
"""Ask not what your country can do for you,
but what you can do for your country""" ]
input.each_index {|i| assert_equal(ans[i], longest_dup_substr(input[i]))}
end
end
word_frequency_count_input.txt
