16801


文章の一部を縦に読んだり横に読んだりすると、ある言葉が見つかることがあります。  
このことをより一般的に次のように考えることにします。

①文章（縦書きと横書きがありますが、ここでは横書きとします。）を  
x×y行列に文字がおさまったもののように扱う。  
②行列の任意の場所から出発し、 **一つ右もしくは一つ下の文字をたどっていく。**  
注）縦読みや横読みを含んでいますが、斜めに読むことは含んでいません。

さて、指定した文字列が見つかれば、  
"I found it!"  
を出力し、見つからなければ、  
"Not found"  
を出力するものとします。

次に示すコードでは、  
出発点から一つずつ順番に指定した文字列と一致する文字を探している  
のですが、  
xが大きくなっても指定された文字列を高速に探し出せるようにするには  
どうすればよろしいでしょうか？

[code]

    # -*- coding: cp932 -*-
    
    x = 10
    y = 11
    @num = (0..x * y - 1).to_a
    # x×y行列（ただしy列目は番兵をおく）
    ary1 = [
    'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
    'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
    'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
    'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
    'き', 'か', 'ま', 'あ', 'お', 'か', 'ま', 'あ', 'み', 'き', '番兵',
    'あ', 'か', 'ま', 'あ', 'ま', 'き', 'ま', 'あ', 'き', 'あ', '番兵',
    'か', 'ま', 'き', 'あ', 'あ', 'か', 'ま', 'あ', 'ま', 'あ', '番兵',
    'あ', 'か', 'が', 'あ', 'あ', 'か', 'ま', 'あ', 'き', 'あ', '番兵',
    'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'あ', 'が', 'み', '番兵',
    'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'み', '。', '　', '番兵'
    ]
    # ary1を一文字変更
    ary2 = [
    'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
    'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
    'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
    'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
    'き', 'か', 'ま', 'あ', 'お', 'か', 'ま', 'あ', 'み', 'き', '番兵',
    'あ', 'か', 'ま', 'あ', 'ま', 'き', 'ま', 'あ', 'き', 'あ', '番兵',
    'か', 'ま', 'き', 'あ', 'あ', 'か', 'ま', 'あ', 'ま', 'あ', '番兵',
    'あ', 'か', 'が', 'あ', 'あ', 'か', 'ま', 'あ', 'き', 'あ', '番兵',
    'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'あ', 'が', 'ま', '番兵',
    'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'み', '。', '　', '番兵'
    ]
    ary3 = [
    'あ', 'か', 'ま', 'き', 'が', 'み', 'ま', 'き', 'ま', 'き', '番兵',
    'あ', 'か', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', '番兵',
    'か', 'ま', 'ま', 'が', 'あ', 'か', 'ま', 'あ', 'ま', 'み', '番兵',
    'あ', 'き', 'が', 'み', 'あ', 'お', 'ま', 'き', 'が', 'み', '番兵',
    'き', 'か', 'ま', 'あ', 'お', 'ま', 'き', 'が', 'み', 'き', '番兵',
    'あ', 'か', 'ま', 'あ', 'ま', 'き', 'が', 'あ', 'き', 'あ', '番兵',
    'か', 'ま', 'き', 'あ', 'あ', 'が', 'み', 'き', 'ま', 'あ', '番兵',
    'あ', 'か', 'が', 'あ', 'あ', 'み', 'き', 'ま', 'き', 'あ', '番兵',
    'あ', 'か', 'み', 'あ', 'あ', 'か', 'ま', 'き', 'が', 'ま', '番兵',
    'あ', 'か', 'ま', 'お', 'ま', 'き', 'が', 'が', '。', '　', '番兵'
    ]
    
    def search(ary, i, str_ary, str)
      i_ary = []
      str_ary.each{|m|
        # strを右と下から探す
        ([m + 1, m + i] & @num).each{|n|
          i_ary.push(n) if ary[n] == str
        }
      }
      i_ary
    end
    
    def find_the_word(ary, i, str)
      str_size = str.size
      message = 'Not found'
      @num.each{|x|
        if ary[x] == str[0]
          s = 1
          next_a = search(ary, i, [x], str[s])
          while next_a.size > 0 && s < str_size - 1
            a = next_a
            s += 1
            next_a = search(ary, i, a, str[s])
          end
          if next_a.size > 0 && s == str_size - 1
            message = 'I found it!'
            break
          end
        end
      }
      message
    end
    
    p 'ary1'
    p find_the_word(ary1, y, 'あかまきがみあおまきがみきまきがみ')
    p 'ary2'
    p find_the_word(ary2, y, 'あかまきがみあおまきがみきまきがみ')
    p 'ary3'
    p find_the_word(ary3, y, 'あかまきがみあおまきがみきまきがみ')
    
[/code]

出力結果  
"ary1"  
"I found it!"  
"ary2"  
"Not found"  
"ary3"  
"Not found"

（追記）  
「xが大きくなっても指定された文字列を高‌​速に探し出せるようにする」とありますが、具体的にどれくらいの大きさのものをどれくらいのスピードで探し出したいのか、具体的なゴールはありますか？  
に対する回答ですが、  
xが1000位でも必ず１秒以内で結果が出力される  
ように変更したいです。  
現状だと、（x = 1010 に変更し、）  
ary2を100回繰り返したものにary1を加えたものに対して、  
"I found it!"と表示されるまで１秒もかからないのに対し、  
ary3を100回繰り返したものにary1を加えたものに対して、  
"I found it!"と表示されるまで何分も待たないといけません。


CC BY-SA 3.0
2015-09-19T16:19:13.727
16776
2016-02-21T12:47:38.430
2016-02-21T12:47:38.430
5363
5363
question
ruby アルゴリズム
大きな行列から指定された文字列を探し出すには？


上手く実装できていないのですが、次のような考え方で高速化できそうです。

①ある程度意味を持つ文字列※を探すので、指定された文字列の中に  
使用頻度の少ない文字があるはずなので、その文字を探す。  
※指定された文字列が「おらおらおらおらおら」のようなものではないとする。

②行列の中から、使用頻度の少ない文字を見つけ、  
その前の文字を左と上から、その後の文字を右と下から  
探していく。

質問の例だと、「か」（または「お」）を行列の中から見つけ、  
その前の文字「あ」が左または上にあるか、その後の文字「ま」が右または下にあるか  
調べていくことになる。

（上記アルゴリズムの弱点）  
行列に使用頻度の少ない文字が多数含まれている場合、あまり有用ではない。


CC BY-SA 3.0
2015-09-20T04:30:31.780
16788
2015-09-20T04:36:55.713
2015-09-20T04:36:55.713
5363
5363
16776
answer


動的計画法でどうでしょう。

[code]

    # -*- coding: utf-8 -*-
    
    W = 11
    ARY1 = # 出題のary1
    ARY2 = # 出題のary2
    ARY3 = # 出題のary3
    
    def left(pos)
        pos - 1
    end
    
    def above(pos)
        pos - W
    end
    
    def union(a, b)
        (a + b).uniq
    end
    
    def dpsearch(ary, str)
        ss = Array.new(ary.size, [].freeze)
        last = str.size - 1
    
        W.upto(ary.size - 1) do |pos|
            pre = union(ss[left(pos)], ss[above(pos)]) + [-1]
            ss[pos] = pre.map { |s| s+1 }.select { |s| ary[pos] == str[s] }
            return pos if ss[pos].include? last
        end
    
        nil
    end
    
    [ARY1, ARY2, ARY3, ARY2 * 100 + ARY1, ARY3 * 100 + ARY1].each { |ary|
        ary = Array.new(W, '番兵') + ary # 番兵行を上に追加
        pos = dpsearch(ary, 'あかまきがみあおまきがみきまきがみ')
        if pos
            puts "Found (last char #{ary[pos]} at #{pos % W}, #{pos / W - 1})"
        else
            puts "Not found"
        end
    }
    
[/code]

出力結果はこうなります:

[code]

    Found (last char み at 9, 8)
    Not found
    Not found
    Found (last char み at 9, 12)
    Found (last char み at 9, 1008)
    
[/code]


CC BY-SA 3.0
2015-09-20T14:20:15.807
16801
2015-09-20T14:20:15.807
9464
16776
answer