共通部分文字列をカウント | アルゴリズム [AOJ 528][Ruby/Python][文字列操作]


引き続きプログラミングの基礎体力づくりと、Pythonの勉強を兼ねてアルゴリズムを勉強中です。今回は『共通部分文字列をカウントする方法』について勉強しました。AIZU Online Judgeで対応している問題は、『Common Sub-String』です。アルゴリズムというよりは頭の体操的なパズル問題ですが、ある程度速度の早いプログラムを書くのには工夫が必要だなと痛感しています。


🤔 AOJ問題

Common Sub-String

Aizu Online Judge。2個の文字列が与えられたとき、 両方の文字列に含まれる文字列のうちもっとも長いものを探し、 その長さを答えるプログラム。

👽 Rubyコード

loop do
s, t = gets.chomp, gets.chomp rescue break
s, t = t, s if s.length > t.length
max_l = (s.chars & t.chars).map do |a|
[s.count(a), t.count(a)].min
end.inject(:+).to_i
answer = 0
0.upto(t.length).each do |i|
break if t.length - i <= answer
max = [max_l+1, t.length - i + 1].min - 1
(answer + 1).upto(max) do |j|
if s.include?(t[i...i+j])
answer = j
else
break
end
end
end
puts answer
end

🍮 Pythonコード

while True:
try:
s, t = raw_input(), raw_input()
if len(s) < len(t): s, t = t, s
MAXL = sum(min(s.count(i), t.count(i)) for i in set(list(s)) & set(list(t)))
ans = 0
for sp in range(len(t)):
if len(t) - sp <= ans:
break
for l in range(ans+1, min(MAXL+1, len(t)-sp+1)):
if t[sp:sp+l] in s:
ans = l
else:
break
print ans
except:
break

🎃 GitHubリポジトリ

当面はAOJを解きながら、アルゴリズムの再勉強をしていくつもりです。Ruby/PythonでのAOJの回答は下のリポジトリに保存しておきます。もしツッコミとかあればぜひ^^

morizyun/aoj-ruby-python - GitHub

📚 おすすめの書籍