Find possible factors from two elements of a shuffle product; see https://math.stackexchange.com/questions/3609799.

Question3609799.java

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class Question3609799 {
    final static int k = 20;
    final static int l = 30;
    final static int n = k + l;
    
    final static int nbases = 4;
    
    final static Random random = new Random ();
    
    static class Hypothesis {
        byte [] W = new byte [k];
        byte [] Z = new byte [l];
        int mw, nw;
        
        public Hypothesis() {}

        public Hypothesis(Hypothesis h) {
            W = h.W.clone();
            Z = h.Z.clone();
            mw = h.mw;
            nw = h.nw;
        }

        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + Arrays.hashCode(W);
            result = prime * result + Arrays.hashCode(Z);
            result = prime * result + mw;
            result = prime * result + nw;
            return result;
        }

        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Hypothesis other = (Hypothesis) obj;
            if (!Arrays.equals(W, other.W))
                return false;
            if (!Arrays.equals(Z, other.Z))
                return false;
            if (mw != other.mw)
                return false;
            if (nw != other.nw)
                return false;
            return true;
        }
    }
    
    public static void main(String [] args) {
        byte [] M = new byte [n];
        byte [] N = new byte [n];
        byte [] W = new byte [k];
        byte [] Z = new byte [l];
        
        for (byte [] a : new byte [] [] {W,Z})
            for (int i = 0;i < a.length;i++)
                a [i] = (byte) random.nextInt(nbases);
        
        for (byte [] a : new byte [] [] {M,N}) {
            boolean [] fromW = new boolean [n];
            for (int i = 0;i < k;i++)
                for (;;) {
                    int which = random.nextInt(n);
                    if (!fromW [which]) {
                        fromW [which] = true;
                        break;
                    }
                }
            int wIndex = 0;
            int zIndex = 0;
            for (int i = 0;i < n;i++)
                a [i] = fromW [i] ? W [wIndex++] : Z [zIndex++];
        }
        
        System.out.println("W: " + toString(W));
        System.out.println("Z: " + toString(Z));
        System.out.println("M: " + toString(M));
        System.out.println("N: " + toString(N));
        
        Set<Hypothesis> hypotheses = new HashSet<>();
        
        hypotheses.add(new Hypothesis());
        
        for (int i = 0;i < n;i++) {
            Set<Hypothesis> newHypotheses = new HashSet<>();
            for (Hypothesis h : hypotheses) {
               if (h.mw < k && (h.mw >= h.nw || h.W [h.mw] == M [i])) { // M could be W
                   Hypothesis newH = new Hypothesis(h);
                   newH.W [newH.mw++] = M [i];
                   newHypotheses.add(newH);
               }
               if (i - h.mw < l && (h.mw <= h.nw || h.Z [i - h.mw] == M [i])) { // M could be Z
                   Hypothesis newH = new Hypothesis(h);
                   newH.Z [i - newH.mw] = M [i];
                   newHypotheses.add(newH);
               }
            }

            hypotheses = newHypotheses;
            
            newHypotheses = new HashSet<>();

            for (Hypothesis h : hypotheses) {
               if (h.nw < k && (h.nw >= h.mw || h.W [h.nw] == N [i])) { // N could be W
                   Hypothesis newH = new Hypothesis(h);
                   newH.W [newH.nw++] = N [i];
                   newHypotheses.add(newH);
               }
               // -1 is because hypotheses for m have already been updated,
               // so we need the comparison i - h.nw <= i + 1 - h.mw
               if (i - h.nw < l && (h.nw <= h.mw - 1 || h.Z [i - h.nw] == N [i])) { // N could be Z
                   Hypothesis newH = new Hypothesis(h);
                   newH.Z [i - newH.nw] = N [i];
                   newHypotheses.add(newH);
               }
            }
            hypotheses = newHypotheses;
            
            System.out.println("position " + i + " out of " + n + " : " + hypotheses.size() + " active hypotheses");
        }
        
        System.out.println(hypotheses.size() + " solutions");

        boolean found = false;
        for (Hypothesis h : hypotheses)
            if (Arrays.equals(h.W, W) && Arrays.equals(h.Z, Z))
                found = true;
        System.out.println("original " + (found ? "" : "not ") + "found");
    }
    
    static char [] bases = {'A','C','G','T'};
    
    static String toString(byte [] a) {
        StringBuffer buffer = new StringBuffer();
        for (byte b : a)
            buffer.append(b < bases.length ? bases [b] : (char) (b + 'a'));
        return buffer.toString();
    }
}