def rhs_can_maybe_derive(rhs_a, rhs_b):
  """Return False if rhs_a cannot be used in a derivation of rhs_b.

  This function uses a fast approximation based on terminal sequence overlap
  to identify cases where `rhs_a` could never be used in a derivation of
  `rhs_b`.

  For example, given `rhs_a`:

  "foo NT foo NT"

  There is a derivation that includes `rhs_a` that derives:

  "foo bar bar foo NT"

  But there is no derivation that includes `rhs_a` and derives:

  "foo NT dax NT"

  Args:
    rhs_a: Tuple of strings for source or target of QCFGRule.
    rhs_b: Same type as rhs_a.

  Returns:
    False if rhs_a cannot be used in a derivation of rhs_b.
  """
  len_rhs_a = len(rhs_a)
  len_rhs_b = len(rhs_b)
  if len_rhs_a > len_rhs_b:
    return False
  if not rhs_a or not rhs_b:
    return False

  # Represent search state with backtracking.
  rhs_a_idx_backtrack = 0
  rhs_a_idx = 0
  rhs_b_idx_backtrack = 0
  rhs_b_idx = 0

  while True:
    if rhs_a_idx >= len_rhs_a:
      # Completed matching all terminals.
      return True

    if rhs_b_idx >= len_rhs_b:
      # Failed to match all terminal sequences.
      return False

    # Fail early if match cannot be made based on remaining length.
    if (len_rhs_a - rhs_a_idx) > (len_rhs_b - rhs_b_idx):
      return False

    a_symbol = rhs_a[rhs_a_idx]
    b_symbol = rhs_b[rhs_b_idx]

    if a_symbol == b_symbol:
      # Matched next terminal symbol, increment indexes.
      rhs_a_idx += 1
      rhs_b_idx += 1
    elif a_symbol == qcfg_rule.NT_2 or a_symbol == qcfg_rule.NT_1:
      # Completed matching terminal sequence.
      # Increment backtrack indexes past this sequence.
      rhs_a_idx += 1
      rhs_a_idx_backtrack = rhs_a_idx
      rhs_b_idx_backtrack = rhs_b_idx
    else:
      # Symbols do not match, backtrack.
      rhs_a_idx = rhs_a_idx_backtrack
      rhs_b_idx_backtrack += 1
      rhs_b_idx = rhs_b_idx_backtrack
Return False if rhs_a cannot be used in a derivation of rhs_b.

  This function uses a fast approximation based on terminal sequence overlap
  to identify cases where `rhs_a` could never be used in a derivation of
  `rhs_b`.

  For example, given `rhs_a`:

  "foo NT foo NT"

  There is a derivation that includes `rhs_a` that derives:

  "foo bar bar foo NT"

  But there is no derivation that includes `rhs_a` and derives:

  "foo NT dax NT"

  Args:
    rhs_a: Tuple of strings for source or target of QCFGRule.
    rhs_b: Same type as rhs_a.

  Returns:
    False if rhs_a cannot be used in a derivation of rhs_b.
  
language/compgen/nqg/model/induction/rule_utils.py