# Variant of Post's Correspondence Problem

I'm trying to solve the same problem as this fellow, in Java. The problem, in short, is:

Given pairs $(a_1,b_1),\dots,(a_k,b_k)$ of strings, find a sequence $s_1, \dots, s_m$ such that

• $a_{s_1} \dots a_{s_m} = b_{s_1} \dots b_{s_m}$.

• for all $i \ne j, s_i \ne s_j$.

If there is a shortest such sequence, the corresponding string shall be outputted. If there are several strings of equal length, the lexicographically smallest (?) one shall be outputted. The original problem is given here, and a C++ solution (which I don't understand because I don't know C++, and there are no comments) can be seen here.

If I've understood correctly, the second requirement means the i:th and j:th substrings used cannot be the same (if i and j are the same).

I'm able to solve the given sample cases, but something goes wrong quite early with the other test cases (which are unknown). This is my approach:

Load the pairs into String[] a,b. Create ArrayList<String> aOut, bOut (initialize both with new), and do:

for each pair i, if a[i].compareTo(b[i]) == 0, add them to aOut and bOut, resp.


We can also keep track of the length of the shortest pair in aOut/bOut, shortestOut, and prune aOut/bOut accordingly. These are pairs which on their own are possible outputs.

Next, we look at pairs that can be used to build matching strings from, call them bases. Such a pair (a,b) must be such that a is a substring of b or b a substring of a, counting from the first character (using regionMatches()). The longest of a, b must be strictly shorter than shortestOut.

Let's call the pairs that are neither outputs nor base pairs "block pairs". At this point, suppose we have the output pair and base pair indices (as they appear in the a[],b[]) recorded, as well as the block pair indices, in, say, outIndex, baseIndex, blockIndex. How do we build upon the bases effectively and without missing possible cases?

Here's basically how I did:

for each base pair i,
for each block pair j, // if baseIndex.get(i) != blockIndex.get(j), do this loop

aTmp = a[baseIndex.get(i)] + a[blockIndex.get(j)] // similarly for bTmp

if (aTmp.compareTo(bTmp) == 0 && their length is at most shortestOut)
else if (one is a substring of the other as before
&& their length is strictly less than shortestOut)
{
add them as a new base pair
record that the current block pair can not be used to expand the new base pair
}


Finally we decide which of the pairs is shortest etc.

So finally my QUESTION (which isn't really Java-specific, whence my asking it here): is this a good way of going about it, or am I missing some crucial detail which finding a solution much easier? Indeed, will it do the trick? My solution runs out of memory which is probably due to the list of base pairs growing indefinitely, because I've some special case. Meanwhile the C++ solution, as far as I can tell, doesn't do the above or anything close to it. So, yeah, hints, tips and tricks, are most welcome, thank you.

• Your question is still meaningful only to people versed in Java, since you're using (for example) compareTo and equating it to 0. – Yuval Filmus Jul 1 '17 at 21:21
• As an aside, Java and C++ are not so different, and it's better if you were able to understand basic C++ code. – Yuval Filmus Jul 1 '17 at 21:21
• The version of your problem when you are allowed to repeat base pairs is quite hard; indeed, undecidable. I'm not sure there is any shortcut here beyond exploring the search tree using partial matches, which seems to be the approach you are advocating. – Yuval Filmus Jul 1 '17 at 21:23
• One thing you can try is "meet in the middle", though it's not clear it will be effective here. – Yuval Filmus Jul 1 '17 at 21:25