Consider a fixed finite alphabet $A$. I am given as input two strings $S_1$ and $S_2$ on $A$, and a string $S$ on $A$. It is of course possible in PTIME to determine whether $S_1$ is a (non-contiguous) subsequence of $S$, and likewise for $S_2$. But now I ask whether I can have matches $m_1$ and $m_2$ of $S_1$ and $S_2$ as subsequences of $S$ ($m_k$ for $k \in \{1, 2\}$ is a strictly increasing function from $\{1, \ldots, |S_k|\}$ to $\{1, \ldots, |S|\}$ such that, for all $i$, $S_k[i]$ and $S[m_k(i)]$ are the same letter) such that $m_1$ and $m_2$ are disjoint (that is, their images are disjoint). Intuitively, no character of $S$ matches $S_1$ and $S_2$ simultaneously.
Is there a PTIME algorithm to determine this (in the size of the input $S_1, S_2, S$), or can it be shown to be NP-hard? I would suspect it is NP-hard but I cannot see a reduction.
In case it is in PTIME, what about the straightforward generalization, for a constant $k$, where $k$ strings are given as input and I ask for the existence of pairwise disjoint matches of all $k$ strings?
(This problem is a bit related to How hard is unshuffling a string? except the candidate strings can be different, are provided as input, and are not required to cover the entire string $S$.)