$count_try = 0
def count_try(re, str)
  $count_try = 0
  rx_ends(re, str, 0)
  $count_try
end

def scanstr(s, r)
  s = s.split(//)
  beg = 0
  result = []
  while md = cap_include(r, s, beg)
    m = md[:all].begin
    n = md[:all].end
    result << s[m...n].join
    beg = n
    if m == n
      if beg == s.length
        break
      else
        beg += 1
      end
    end
  end
  result
end

def subst(s, r)
  s = s.split(//)
  md = cap_include(r, s)
  return s.join if !md
  h = {}
  md.each {|k, v| h[k] = s[v].join }
  m = md[:all].begin
  n = md[:all].end
  s[0...m].join +
  yield(s[m...n].join, h) +
  s[n..-1].join
end

def gsubst(s, r)
  s = s.split(//)
  beg = 0
  result = []
  while md = cap_include(r, s, beg)
    m = md[:all].begin
    n = md[:all].end
    h = {}
    md.each {|k,v| h[k] = s[v].join }
    result += s[beg...m]
    result << yield(s[m...n].join, h)
    beg = n
    if m == n
      if beg == s.length
        break
      else
        result << s[beg]
        beg += 1
      end
    end
  end
  result += s[beg..-1]
  result.join
end

def cap_include(r, str, beg=0)
  str = str.split(//) if str.respond_to? :to_str
  md0 = { :search_start => beg...beg }
  beg.upto(str.length) {|b|
    try(r, str, b, md0) {|e, md|
      md = md.dup
      md[:all] = b...e
      return md 
    }
  }
  nil
end

def cap_exact(r, str)
  str = str.split(//)
  try(r, str, 0, {}) {|e, md|
    if str.length == e
      md = md.dup
      md[:all] = 0...e
      return md 
    end
  }
  nil
end

def match_include(r, str)
  str = str.split(//)
  0.upto(str.length) {|b|
    try(r, str, b, {}) {|e, md|
      return b...e
    }
  }
  nil
end

def match_exact(r, str)
  str = str.split(//)
  try(r, str, 0, {}) {|e, md|
    if str.length == e
      return 0...e
    end
  }
  nil
end

def rx_ends(re, str, pos)
  a = []
  # str.split(//) returns an array which contains characters of str.
  try(re, str.split(//), pos, {}) {|pos2, md2| a << pos2 }
  a
end

$indent = 0
def try(re, str, pos, md, &b)
  #printf "%s start %d %s\n", ' ' * $indent, pos, re.inspect
  $indent += 1
  $count_try += 1
  ret = if re.respond_to? :to_str
    yield pos+1, md if str[pos] == re
  else
    case re[0]
    when :empset
      # nothing to do
    when :empstr
      yield pos, md
    when :string_start
      yield pos, md if pos == 0
    when :string_end
      yield pos, md if pos == str.length
    when :line_start
      yield pos, md if pos == 0 || (pos < str.length && str[pos-1] == "\n")
    when :line_end
      yield pos, md if pos == str.length || str[pos] == "\n"
    when :search_start
      yield pos, md if pos == md[:search_start].begin
    when :cat
      try_cat(re, str, pos, md, &b)
    when :alt
      try_alt(re, str, pos, md, &b)
    when :rep
      try_rep(re, str, pos, md, &b)
    when :rep_lazy
      try_rep_lazy(re, str, pos, md, &b)
    when :plus
      try_plus(re, str, pos, md, &b)
    when :plus_lazy
      try_plus_lazy(re, str, pos, md, &b)
    when :capture
      try_capture(re, str, pos, md, &b)
    when :opt
      try_opt(re, str, pos, md, &b)
    when :opt_lazy
      try_opt_lazy(re, str, pos, md, &b)
    when :times
      try_times(re, str, pos, md, &b)
    when :moretimes
      try_moretimes(re, str, pos, md, &b)
    when :anychar
      yield pos+1, md if pos < str.length
    when :atomic
      try_atomic(re, str, pos, md, &b)
    when :rep_possessive
      try([:atomic, [:rep, re[1]]], str, pos, md, &b)
    when :opt_possessive
      try([:atomic, [:opt, re[1]]], str, pos, md, &b)
    when :plus_possessive
      try([:atomic, [:plus, re[1]]], str, pos, md, &b)
    else
      raise ArgumentError, "unexpected: #{re.inspect}"
    end
  end
  ret
ensure
  $indent -= 1
  #printf "%s end   %d %s\n", ' '*$indent, pos, re.inspect
end

def try_atomic(re, str, pos, md)
  try(re[1], str, pos, md) {|pos2, md2|
    yield pos2, md2
    return
  }
end

def try_cat(re, str, pos, md, &b)
  if re.length == 1
    yield pos, md
  else
    re2 = [:cat] + re[2..-1]
    try(re[1], str, pos, md) {|pos2, md2|
      try_cat(re2, str, pos2, md2, &b)
    }
  end
end

def try_alt(re, str, pos, md, &b)
  1.upto(re.length-1) {|i|
    try(re[i], str, pos, md, &b)
  }
end

def try_rep(re, str, pos, md, &b)
  try(re[1], str, pos, md) {|pos2, md2|
    try(re, str, pos2, md2, &b) if pos < pos2
  }
  yield pos, md
end

def try_rep_lazy(re, str, pos, md, &b)
  yield pos, md
  try(re[1], str, pos, md) {|pos2, md2|
    try(re, str, pos2, md2, &b) if pos < pos2
  }
end

def try_plus(re, str, pos, md, &b)
  try(re[1], str, pos, md) {|pos2, md2|
    try([:rep, re[1]], str, pos2, md2, &b)
  }
end

def try_plus_lazy(re, str, pos, md, &b)
  try(re[1], str, pos, md) {|pos2, md2|
    try([:rep_lazy, re[1]], str, pos2, md2, &b)
  }
end

def try_opt(re, str, pos, md, &b)
  try(re[1], str, pos, md, &b)
  yield pos, md
end

def try_opt_lazy(re, str, pos, md, &b)
  yield pos, md
  try(re[1], str, pos, md, &b)
end

def try_times(re, str, pos, md, &b)
  m = re[1]
  n = re[2]
  r = re[3]
  if 0 < n
    try(r, str, pos, md) {|pos2, md2|
      try([:times, m-1, n-1, r], str, pos2, md2, &b)
    }
  end
  yield pos, md if m <= 0
end

def try_moretimes(re, str, pos, md, &b)
  m = re[1]
  r = re[2]
  try(r, str, pos, md) {|pos2, md2|
    try([:moretimes, m-1, r], str, pos2, md2, &b) if pos < pos2
  }
  yield pos, md if m <= 0
end

def try_capture(re, str, pos, md, &b)
  name = re[1]
  r = re[2]
  try(r, str, pos, md) {|pos2, md2|
    md3 = md2.dup
    md3[name] = pos...pos2
    yield pos2, md3
  }
end

def rx_exact(r, str)
  str = str.split(//)
  try(r, str, 0, {}) {|e, md|
    return true if str.length == e
  }
  false
end

def rx_include(r, str)
  str = str.split(//)
  0.upto(str.length) {|b|
    try(r, str, b, {}) {|e, md|
      return true
    }
  }
  false
end