共通部分文字列をカウント | アルゴリズム [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< span>    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 answerend
    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:< span>        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
        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

🖥 VULTRおすすめ

「VULTR」はVPSサーバのサービスです。日本にリージョンがあり、最安は512MBで2.5ドル/月($0.004/時間)で借りることができます。4GBメモリでも月20ドルです。 最近はVULTRのヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります！

📚 おすすめの書籍