pattern := aaba
string := foofoocatfoo
symbol_table := {}

void Matches(pattern, haystack, symbol_table) {
  if (pattern.size() == 0 &&  haystack.size() == 0) {
    return true;
  }

  string v;
  if (symbol_table.Contains(pattern[0])) {
    v = symbol_table[pattern[0]];

    // Check if haystack starts with v.
    if (HasPrefix(v, haystack)) {
      return Matches(pattern[1:], haystack[v.size():], symbol_table);
    }  else {
      return false;
    }
  }

  for (int i = 0; i < haystack.size(); ++i) {
    symbol_table[pattern[0]] = haystack[:i];
    if (Match(pattern[1:], haystack[i:], symbol_table)) {
      return true;
    }
  }
  symbol_table[pattern[0]] = null;
  return false;
}