The main advantage of Constraint Programming (CP) approaches for sequential\npattern mining (SPM) is their modularity, which includes the ability to add new\nconstraints (regular expressions, length restrictions, etc). The current best\nCP approach for SPM uses a global constraint (module) that computes the\nprojected database and enforces the minimum frequency; it does this with a\nfiltering algorithm similar to the PrefixSpan method. However, the resulting\nsystem is not as scalable as some of the most advanced mining systems like\nZaki's cSPADE. We show how, using techniques from both data mining and CP, one\ncan use a generic constraint solver and yet outperform existing specialized\nsystems. This is mainly due to two improvements in the module that computes the\nprojected frequencies: first, computing the projected database can be sped up\nby pre-computing the positions at which an symbol can become unsupported by a\nsequence, thereby avoiding to scan the full sequence each time; and second by\ntaking inspiration from the trailing used in CP solvers to devise a\nbacktracking-aware data structure that allows fast incremental storing and\nrestoring of the projected database. Detailed experiments show how this\napproach outperforms existing CP as well as specialized systems for SPM, and\nthat the gain in efficiency translates directly into increased efficiency for\nother settings such as mining with regular expressions.\n