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

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

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

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

# -*- 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, 'あかまきがみあおまきがみきまきがみ')

出力結果
"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!"と表示されるまで何分も待たないといけません。