Long paths make pattern-counting hard, and deep trees make it harder

Abstrakt

We study the counting problem known as #PPM, whose input is a pair of permutations π and τ (called pattern and text, respectively), and the task is to find the number of subsequences of τ that have the same relative order as π.

Klíčová slova

• Permutation
• pattern matching