class String
  # パターンを一ヶ所で照合: 超単純実装
  def simplest_match_at? (pattern, shift)           # 一番単純なやり方
    match = true
    pattern.each_char.with_index do |character, index|
      match &&= character==self[shift+index]        # 一致の論理総積
    end
    match
  end

  # パターンを一ヶ所で照合: 素朴な実装
  def simple_match_at? (pattern, shift)
    pattern.each_char.with_index do |character, index|
      return false if character!=self[shift+index]  # 速い段階で打ち切る
    end
    true
  end

  # パターンを一ヶ所で照合: Ruby の内部実装を使用
  def internal_match_at? (pattern, shift)
    self[shift, pattern.length] == pattern
  end

  # 途中から一つの照合場所の発見
  def simple_match_from (pattern, start)
    start.upto(length-pattern.length) do |shift|
      return shift if simple_match_at?(pattern, shift) # simple_match_at?
    end                                         # の代わりに simplest_match_at?
    nil                                         # や internal_match_at? も使用可能
  end
  
  # 最初の照合場所の発見
  def simple_match (pattern)
    simple_match_from(pattern, 0)
  end

  # 全ての照合場所の発見
  def simple_match_all (pattern)
    shifts = []
    shift = -1
    while shift = simple_match_from(pattern, shift+1)
      shifts << shift
    end
    shifts
  end
  
  # Rabin-Karp
  protected
  def rk_hash (b, d)
    each_codepoint.inject(0) do |memo, code|
      memo = (memo*b + code) % d      ## each_codepoint は文字の番号を返す
    end
  end
  
 public
  def match_rabin_karp (pattern)
    base = 256                                     # 1バイトの文字コードが前提
    divisor = 2**14+43                                # 素数
    m = pattern.length
    bm1_mod_d = base**(m-1) % divisor
    pattern_hash = pattern.rk_hash(base, divisor)
    sliding_hash = self[0, m].rk_hash(base, divisor)
    0.upto(length-pattern.length) do |s|
      return s if pattern_hash==sliding_hash and self[s, m]==pattern
      sliding_hash -= self[s].ord * bm1_mod_d   ## ord は文字の番号を返す
      sliding_hash *= base
      sliding_hash += self[s+m].ord
      sliding_hash %= divisor
    end
    nil
  end



  # Knuth-Morris-Pratt
  # find length of the longest non-trivial prefix that matches a suffix of the string
  def match_prefix_suffix
    1.upto(length) do |shift|
      ml = length - shift               # 比較の長さ
      return ml if self[0,ml]==self[shift,ml]
    end
    0
  end
  
  def prepare_kmp_shifts
    (0..(length-1)).collect do |matched|  # matched: 既にマッチ済みの文字数
      self[0,matched].match_prefix_suffix
    end
  end
  
  def prepare_kmp
    shifts = prepare_kmp_shifts; shifts[0] = -1
    shifts.each_with_index do |s, i|
      shifts[i] = shifts[s]  if s!=-1 and self[i]==self[s]
    end
  end
  
  public
  def show_kmp_preparation
    w = length>10 ? length : 10
    shifts = prepare_kmp_shifts
    puts "preparing to match pattern \"#{self}\""
    next_pattern_index = prepare_kmp
      puts "%5s  %#{w}s  %-4s  %-10s  %4s  %4s" %
            ['index', 'matched', 'char', 'self-match', '*fix', 'next']
    each_char.with_index do |char, i|
      puts "%5d  %#{w}s  %-4c  %-10s  %4d  %4d" %
             [i, self[0,i], self[i], self[0,shifts[i]], shifts[i], next_pattern_index[i]]
    end
    puts
  end

  def match_knuth_morris_pratt (pattern)
    next_table = pattern.prepare_kmp      ## next は予約語
    text_index = pattern_index = 0
    while text_index < length
      if self[text_index] == pattern[pattern_index]
        text_index += 1; pattern_index += 1
        return text_index-pattern_index if pattern_index==pattern.length
      else
        pattern_index = next_table[pattern_index]
        if pattern_index == -1
          text_index += 1
          pattern_index = 0
        end
      end
    end
    nil
  end
end

if __FILE__ == $0                   ## 以下は直接呼出しのみ
  'AOYAOA'.show_kmp_preparation
  'ABRACADABRA'.show_kmp_preparation
  'AAAABAAAAAB'.show_kmp_preparation
  'AAAAAAAAAAA'.show_kmp_preparation

  require 'benchmark'

  text = 'a' * 20000 + 'b'
  pattern = 'a' * 100 + 'b'

  Benchmark.bm(6) do |r|
    r.report('simple') { text.simple_match pattern }
    r.report('R-K   ') { text.match_rabin_karp pattern }
    r.report('KMP   ') { text.match_knuth_morris_pratt pattern }
  end
end