postsche_korrespondenzproblem.java

import java.util.Arrays;

public class PCP {
    final static int MAX_SIZE = 999999;
    public static void main(String[] args) {
        Tupel stein1 = new Tupel("11", "0", "a");
        Tupel stein2 = new Tupel("11", "111", "b");
        Tupel stein3 = new Tupel("1001", "1", "c");
        breitensuche(stein1, stein2, stein3);

        stein1 = new Tupel("01", "1001", "a");
        stein2 = new Tupel("10", "111", "b");
        stein3 = new Tupel("1111", "111", "c");
        Tupel stein4 = new Tupel("1001", "010", "d");
        breitensuche(stein1, stein2, stein3, stein4);

        stein1 = new Tupel("0", "1", "a");
        stein2 = new Tupel("01", "0", "b");
        stein3 = new Tupel("1", "101", "c");
        breitensuche(stein1, stein2, stein3);
    }

    static void breitensuche(Tupel... steine) {
        Tupel neue_kombinationen[] = new Tupel[MAX_SIZE];
        int i = 0;
        neue_kombinationen[i++] = new Tupel("", "", "");

        Tupel kombinationen[] = new Tupel[MAX_SIZE];

        while(true) {
            kombinationen = Arrays.copyOf(neue_kombinationen, MAX_SIZE);
            neue_kombinationen = new Tupel[MAX_SIZE];
            i = 0;

            for (Tupel kombination : kombinationen) {
                if (kombination == null) break;
                for (Tupel stein : steine) {
                    String neux = kombination.x.concat(stein.x);
                    String neuy = kombination.y.concat(stein.y);

                    if (neux.equals(neuy)) {
                        System.out.println("x: " + neux + " y: " + neuy + " name: " + kombination.name + stein.name);
                        return;
                    }

                    int laenge = Math.min(neux.length(), neuy.length());
                    if (neux.substring(0, laenge).equals(neuy.substring(0, laenge))) {
                        neue_kombinationen[i++] = new Tupel(neux, neuy, kombination.name.concat(stein.name));
                    }
                }
            }
        }
    }

}

public class Tupel {
    String x;
    String y;
    String name;

    public Tupel(String x, String y, String name) {
        this.x = x;
        this.y = y;
        this.name = name;
    }
}