Searching for multiple partial phrases so that one original phrase can not match multiple search phrases
Let's fix some names. Let $q_1, \dots, q_k$ be the query strings and $w_1, \dots, w_n$ the existing phrases. Denote with $w_{i,1}, \dots, w_{i,k_i}$ the words contained in phrase $w_i$, and with $a \sqsubseteq b$ the relation "$a$ is a prefix of $b$".

Currently, you have implemented to obtain this:

$\qquad\displaystyle \{ i \in [1..n] \mid \forall j \in [1..k]\ \exists j' \in [1..k_i].\ q_j \sqsubseteq w_{i,j'}\}$.

Note how the $\exists$-operator does not preclude the same $j'$ for multiple $j$, and that's your problem (as far as I can tell). What you want is

$\qquad\displaystyle \{ i \in [1..n] \mid \exists J = \{j_1, \dots, j_k\} \subseteq [1..k_i]\ \forall j \in [1..k].\ q_j \sqsubseteq w_{i,j_j}\}$.

One way to implement this is to go with the double-indexing I used to describe the problem formally: each node gets the set of labels $(i,j)$ if its corresponding string is a prefix of $w_{i,j}$. Now, $i$ is a match if


every $q_l$ leads to a node with label $(i,\_)$ and
the second components of these labels are pairwise distinct (if there are multiple $(i,\_)$ for a single $q_l$, one has to check if there is a choice fulfilling the condition).


In your example, instead of just adding 6 to all these nodes you list, you'd add (5,1) and (6,1) to the prefixes of programming, and (6,2) to those of puzzles. Now, prog p gives you (5,1), (6,1) for prog and (5,1), (6,1), (6,2) for p; you can exclude 5 because it has the same second component for both query phrases whereas 6 has a "valid" match with (6,1) and (6,2).