Cel mai lung subsir comun

public class LargestCommonSubsequence {
    //private static final String S1 = "ABCBDAB";
    private static final String S1 = "GEORGIANAVULPE";
    // private static final String S1 = "BDABC";

    // private static final String S2 = "BDCABA"; // BCAB
    private static final String S2 = "GINALARESTAURANT"; // GINALE
    // private static final String S2 = "BAFB"; // BAB

    private long numberOfCalls = 0;

    private String findCommonRec(int i, int j, String accumulator) {
        if (numberOfCalls < Long.MAX_VALUE) {
            numberOfCalls++;
        } else {
            System.out.println("numberOfCalls exceeded max!");
        }

        if (i >= S1.length() || j >= S2.length()) {
            return accumulator;
        }

        if (S1.charAt(i) == S2.charAt(j)) {
            return findCommonRec(i+1, j+1, accumulator + S1.charAt(i));
        }

        String common1 = findCommonRec(i+1, j, accumulator);
        String common2 = findCommonRec(i, j+1, accumulator);
        String common3 = findCommonRec(i+1, j+1, accumulator);

        String longest = common1;
        if (longest.length() < common2.length()) {
            longest = common2;
        }
        if (longest.length() < common3.length()) {
            longest = common3;
        }
        return longest;
        // O(2^n) if n == m
    }

    private void findCommonOptimized() {
        // no recursive calls, use table
        int table [][] = new int[S1.length()+1][S2.length()+1];
        for (int i=0; i<S1.length(); i++) {
            for (int j=0; j<S2.length(); j++) {
                if (S1.charAt(i) == S2.charAt(j)) {
                    table[i+1][j+1] = table[i][j] + 1;
                } else {
                    table[i+1][j+1] = Math.max(table[i+1][j], table[i][j+1]);
                }
            }
        }

        printTable(table);
        // table[S1.length()][S2.length()] = lungime rezultat final

        int i = S1.length();
        int j = S2.length();
        StringBuilder result = new StringBuilder();

        // reconstituire substring: parcurgere dreapta jos -> stanga sus
        while (i > 0 && j > 0) {
            // merge adiacent cat timp se pastreaza valoarea curenta
            if (table[i][j] == table[i-1][j]) {
                i--;
            } else if (table[i][j] == table[i][j-1]) {
                j--;
            } else {
                // cand stanga si deasupra au valori diferite de cea curenta
                // atunci trece diagonal si adauga caracterul la rezultat
                assert S1.charAt(i-1) == S2.charAt(j-1);
                result.append(S2.charAt(j - 1));
                i--;
                j--;
            }
        }

        System.out.println("\nresult = " + result.reverse());
        // O(n^2) if n == m
    }

    private void printTable(int table [][]) {
        System.out.print("  ");
        for (int i=0; i<S2.length(); i++) {
            System.out.print(S2.charAt(i) + " ");
        }
        System.out.println();
        for (int i=0; i<=S1.length(); i++) {
            System.out.print(i < S1.length() ? S1.charAt(i) + " " : "  ");
            for (int j=0; j<=S2.length(); j++) {
                System.out.print(table[i][j] + " ");
            }
            System.out.println();
        }
    }

    private void solve() {
        numberOfCalls = 0;
        System.out.println(findCommonRec(0, 0, ""));
        System.out.println("numberOfCalls = " + numberOfCalls + "\n");

        findCommonOptimized();
    }

    public static void main(String args[]) {
        new LargestCommonSubsequence().solve();
    }
}