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

Abstract

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 π.

Keywords

• Permutation
• pattern matching