This problem, or at least one interesting variant of it, is NP-complete even for binary alphabets and word lengths at most logarithmic in the total number $p$ of partition parts, so it's very unlikely that a polynomial-time algorithm can be found. I have some ideas about ways to reduce the $O(p!)$ time complexity of a naive algorithm to "just" exponential, but that will have to wait for another post -- please let me know if that would be interesting.
Promise problem vs. unrestricted decision problem
Your framing of the problem implies that a solution is guaranteed to exist -- that is, you have formulated it as a promise problem, with the promise being that the two partitions do derive from some common underlying string. I wasn't able to make progress on this version of the problem. (This is perhaps not too surprising, since it turns out that checking whether this promise holds for an unrestricted instance is itself hard -- but note that this hardness of verification does not rule out the possibility that a more efficient algorithm exists that takes advantage of the promise in some clever way.)
In the remainder, I'll consider the more general underlying search and decision problems, in which we may not assume that any solution exists. It's possible that this is actually the variant you are interested in anyway -- certainly, if your intention is to actually apply an algorithm for the problem to noisy real-world data, then this is the right variant to consider, since an algorithm that assumes the promise holds is allowed not to terminate on inputs that violate the promise.
Definitions
An unordered partition (subsequently partition) supports a string if concatenating the partition's parts (or words) in some order produces the string. An alignment is an ordered sequence of words from one partition written above an ordered sequence of words from another partition and such that the 2 characters at each horizontal position are equal.
I'll call your problem Reconstruct String from 2 Partitions (RS2P). The search problem version is: Given 2 multisets of words, containing $p_1$ and $p_2$ words, respectively, with each multiset having total length $q$, find a string of length $q$ that they both support, or report that this is impossible. Define $p=p_1+p_2$.
The decision version of this search problem returns YES if some such length-$q$ string exists, and NO otherwise. (Note that the decision and search problems are polynomially equivalent: Given an algorithm for solving the decision problem, the search problem can be solved by trying each of the $p_1p_2$ combinations of words from the first and second partitions and such that one is a prefix of the other as the leftmost part of the solution in turn, and for each such combination removing the shorter word from its partition and cutting off the corresponding first part of the longer word, and solving the decision problem on the remainder; whenever the resulting subproblem has a YES solution, that combination is the leftmost part of a solution to the original problem, and can be fixed in place.)
NP-completeness proof
I'll show NP-completeness by reducing the NP-complete problem of finding a Hamiltonian Cycle in a digraph (HCD) to it. This is research-level original work; if you're interested in publishing academic work that makes use of it, please let me know in a comment so that we can discuss credit.
For simplicity, in this proof I'll consider a variant of the problem in which the alphabet is $\{1, \dots, n\}$, plus a handful of additional special characters ("colours"). The argument can be straightforwardly transferred to the case of a binary alphabet by expanding each character to its $\lceil\log_2(n+4)\rceil$-digit binary representation (these blocks of size $\lceil\log_2(n+4)\rceil$ necessarily align to each other in any solution, since nothing could fill the smaller gap that would otherwise be left).
The basic idea is to represent each arc $(v_i, v_j)$ in the original digraph as a 4-character word $v_ibbv_j$ in partition 1, and set partition 2 to contain $n-1$ 4-character words, one word $bv_iv_ib$ for each vertex $v_i$ except for $v_n$. A path through the original digraph corresponds to a sequence of 4-character words from partition 1 that "match like dominoes" (the last character in one word equals the first character in the next), so some ordering of the $n$ words from partition 2, after being right-shifted by 2 positions, will match them and help to enforce a Hamiltonian Path property. The main difficulty is in dealing with the "leftover edges" in partition 1 in a sufficiently strict way -- specifically, ensuring that the additional gadgets used for collecting them extract individual edges, rather than paths.
Given an instance $G = (V, A)$ of HCD with $n=|V|$ vertices and $m=|A|$ arcs, we construct an instance of RS2P as follows:
- Set the alphabet to be $\{1, \dots, n\} \cup \{w, b, r, g\}$ (the latter can be thought of as white, black, red and green, respectively).
- Set partition 1 to contain the words:
- $v_ibbv_j$ for each arc $(v_i, v_j) \in A$ (the "edge words")
- $w$
- $r$ (the "end word")
- $m-n$ copies of $rg$
- Set partition 2 to contain the words:
- $bv_iv_ib$ for each $1 \le i \le n-1$ (the "Hamiltonian words")
- $wv_nb$ (the "start word")
- $bv_nr$ (the "mid word")
- $\deg_+(v_i)-1$ copies of $gv_ibb$ for each $1 \le i \le n$ (the "out-gathering words"), where $\deg_+(v_i)$ is the outdegree of $v_i$ in $G$
- $\deg_-(v_i)-1$ copies of $v_ir$ for each $1 \le 1 \le n$ (the "in-gathering words"), where $\deg_-(v_i)$ is the indegree of $v_i$ in $G$
Recall that $\sum_i\deg_+(v_i)=\sum_j\deg_-(v_j)=m$, so there are $m-n$ total out-gathering words in partition 2, and the same number of in-gathering words.
A YES answer to the HCD instance $\implies$ a YES answer to the constructed RS2P instance:
We know a HC exists. Let $s_1$ be the string formed by concatenating words from partition 1 in the following order:
- $w$
- All edge words corresponding to edges in the HC, starting from the unique edge in it that leaves $v_n$
- $m-n$ 2-word blocks, in any order, each consisting of:
- $rg$
- An edge word $v_ibbv_j$ corresponding to a "leftover" edge (an edge not partiticipating in the HC)
- $r$
Let $s_2$ be the string formed by concatenating words from partition 2 in the following order:
- $wv_nb$
- All $n-1$ Hamiltonian words, with each matching the two edge words it overlaps in $s_1$
- $bv_nr$
- $m-n$ 2-word blocks, each matching the "leftover" edge $v_ibbv_j$ it overlaps in $s_1$ and consisting of:
The diagram below shows an example digraph with a YES answer, and the solution to its corresponding RS2P construction. Vertices and their corresponding characters are shown in pastel colours.
A YES answer to the constructed RS2P instance $\implies$ a YES answer to the HCD instance:
"Leftover blocks" form a chain of length exactly $m-n$
If $m=n$ then the end word $r$ in partition 1 necessarily aligns with last character of the mid word $bv_nr$ in partition 2, and we are done.
Otherwise, each out-gathering word $gv_ibb$ in partition 2 must align to a word pair $rg|v_ibbv_j$ for some $j$ in partition 1, since partition 1 has no other words besides $rg$ that contain $g$, and the only words in partition 1 beginning with $v_i$ are the edge words. The overhanging $v_j$ that remains in partition 1 can only align to a corresponding in-gathering word $v_jr$ in partition 2, since partition 2 contains no other words beginning with any $v_k$. This implies that in any solution, there exist $m-n$ of these "leftover blocks", each of the form $rg|v_ibbv_j$ "on the top" (in partition 1) and $gv_ibb|v_jr$ "on the bottom" (in partition 2), each having an $r$ character overhanging at the top-left, and an $r$ character overhanging at the bottom-right. The rightmost-ending such block must have its overhanging-on-the-bottom $r$ aligned to the end word $r$ in partition 1, since otherwise it must align with the overhanging-on-the-top $r$ of some other leftover block, implying it is not the rightmost-ending such block: a contradiction. Similarly, the leftmost-beginning such block must have its overhanging-on-the-top $r$ aligned to the end of the mid word $bv_nr$ in partition 2, since otherwise it must align with the overhanging-on-the-bottom $r$ from some other leftover block, implying it is not leftmost-beginning: a contradiction. Since the leftover blocks exhaust the remaining occurrences of $r$ characters in both partitions, their overhangs must overlap sequentially to form a dense chain that begins with the mid word $bv_nr$ in partition 2, contains all $m-n$ leftover blocks with no other words from either partition, and ends on the bottom with a leftover block, the final $r$ of which aligns to the $r$ word on the top. Call this chain of blocks, beginning with the mid word $bv_nr$ jutting out 2 characters to the left on the bottom, and ending "flush" with aligned $r$ characters, the leftover chain.
The leftover chain is at the right end
We now establish that none of the remaining words in partition 2 (and, thus, none of the remaining words in partition 1) can appear to the right of the leftover chain.
With exactly $m-n$ edge words used up inside the leftover chain, $m-(m-n)=n$ edge words, plus the word $w$, remain in partition 1. The start word $wv_nb$ and the $n-1$ Hamiltonian words remain in partition 2.
The leftover chain has a flush right end, so the only way that any word could appear to the right of it is if it would form a flush left end with a word from the other partition, i.e., if one is a prefix of the other. But the only such pair of words with this property is $w$ and $wv_nb$, since all other words remaining in partition 1 begin with some $v_i$, while all other words remaining in partition 2 begin with $b$. But the word $wv_nb$ is 2 characters longer than the word $w$, so stacking them vertically cannot form the rightmost end of the alignment -- and, since all remaining words in both partitions have length 4, the flushness needed to end the alignment cannot be achieved by appending any number of words from either partition. Hence, the leftover chain forms the rightmost part of the alignment, and all remaining words appear to the left of it.
A Hamiltonian Cycle can be read off the top, between $w$ and $r$
A similar parity argument forces the $w$ and $wv_nb$ words to be aligned to each other at the leftmost end of the alignment (any other placement would imply a ragged left end). It follows that the $n-1$ Hamiltonian words that remain in partition 2 must appear on the bottom, in some order, between $wv_nb$ and $bv_nr$. This leaves $4n$ spaces on top, into which the $n$ remaining edge words must slot, with the first forced to be $v_nbbv_i$ for some $i$ on account of the overlap with the start word $wv_nb$, and the last forced to be $v_jbbv_n$ for some $j$ on account of the overlap with the mid word $bv_nr$. The first and last words correspond to edges out of and into vertex $v_n$ in $G$, respectively, and the $n-1$ Hamiltonian words on the bottom guarantee that the intervening $n-2$ edge words above correspond to edges that form a path that visits each vertex exactly once, so a Hamiltonian Cycle can be read off the $n$ edge words on top between $w$ and $r$.
A YES solution to either instance implies a YES solution to the other, and the construction is polynomial-time, so it follows that RS2P is NP-hard for integer alphabets and words of length at most 4, and by the expansion argument given at the top, for binary alphabets and words of length $O(\log p)$. Since a solution to it can be verified in polynomial time, it is also NP-complete. $\blacksquare$
