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