150921(2)

Ruby


縦読み、横読みの一般化

以下のサイトで掲題について質問してみた。
（http://ja.stackoverflow.com/questions/16776/%E5%A4%A7%E3%81%8D%E3%81%AA%E8%A1%8C%E5%88%97%E3%81%8B%E3%82%89%E6%8C%87%E5%AE%9A%E3%81%95%E3%82%8C%E3%81%9F%E6%96%87%E5%AD%97%E5%88%97%E3%82%92%E6%8E%A2%E3%81%97%E5%87%BA%E3%81%99%E3%81%AB%E3%81%AF）

orangecat さんの回答のコードを少しアレンジしてみた。

# -*- coding: cp932 -*-

W = 4
ary1 = [
'す', 'す', 'ま', '番兵',
'き', 'す', 'す', '番兵',
'す', 'き', 'だ', '番兵'
]
ary2 = [
'す', 'す', 'ま', '番兵',
'き', 'す', 'す', '番兵',
'よ', 'め', 'だ', '番兵'
]

def dpsearch(ary, str)
  # 番兵行を上に追加
  ary = Array.new(W, '番兵') + ary
  ss = Array.new(ary.size, [])
  last = str.size - 1
  W.upto(ary.size - 1){|pos|
    pre = (ss[pos - 1] + ss[pos - W]).uniq + [-1]
    # ary[pos] == str[s]のとき、str[0..s]まで一致している
    ss[pos] = pre.map{|s| s + 1}.select{|s| ary[pos] == str[s]}
    if ss[pos].include?(last)
      # posは番兵行を含んでいるが、元々はpos - W
      return pos - W
    end
  }
  nil
end

[ary1, ary2, ary2 * 1000 + ary1].each{|ary|
  pos = dpsearch(ary, 'すすき')
  if pos
    puts "Found (last char #{ary[pos]} at #{pos % W}, #{pos / W})"
  else
    puts "Not found"
  end
}

出力結果
Found (last char き at 1, 2)
Not found
Found (last char き at 1, 3002)