The paper presents an extended efficient algorithm for pattern matching in partially commutative monoids. The complexity analysis and comparisons are provided using proper mathematical notation. The algorithm improves upon previous methods by reducing complexity from O(m2) to O(m × d), where m is the pattern length and d is the dependency degree. For text T and pattern P, the overall complexity of the suggested algorithm is O(|T | + |P |) which coincides with the complexity of pattern matching for free monoids. Meantime the complexity of algorithms based on thr Cartier–Foata canonical form is O(|T | × |P |).
Shoukourian et al. (2026) studied this question.