79124140

Date: 2024-10-25 03:09:19
Score: 0.5
Natty:
Report link

There is indeed an algorithm for finding patterns in trees - more than one. Christoph Hoffman and Michael O'Donnell published a paper about it in 1982: Pattern Matching in Trees. They talk about two algorithms: a top-down one and a bottom-up one. The top-down method reduces tree pattern matching to string matching. They use an Aho-Corasick automaton to "recognize every instance of a path string from a subject tree," where a path string is a path from the root to a leaf. The pseudo-code algorithm is on the 19th page. I'd recommend reading the paper for context. The top-down pattern matching algorithm. I didn't write it, but there's a Java implementation of the top-down algorithm here.

The bottom-up matching method is supposed to generalize the Knuth-Morris-Pratt string matching algorithm. I understand this one less and haven't implemented it, but Hoffman and O'Donnell talk about it, too.

Reasons:
  • Long answer (-0.5):
  • No code block (0.5):
  • Low reputation (0.5):
Posted by: MaroonSphinx