Wypisywanie części wspólnej z dwóch słów.

Cześć razem z grupką znajomych, mamy problem potrzebujemy napisać program który będzie wypisywać część wspólne z ciągów znaków.
Powiedzmy mamy ciągi:
1: AABABB
2: BAABAB
Części wspólne to:
"AA" "AAB" BA" itd...
Musimy wypisać wszystkie. Mamy kilka kodów, potrzebujemy to na zajęcia z algorytmiki, ciężko nam idzie... także nie ukrywam, że jesteśmy słabi.
Studia zaocznie + praca + inne przedmioty = bardzo mało czasu co przy kiepskich wykładach, właśnie tym owocuje.
Mamy to:

package Czesc;

public class Czesc {


    public static void main(String[] args) {
        String tekst1 = "AABABB";
        String tekst2 = "BAABAB";
         
        int dl1 = tekst1.length();
        int dl2 = tekst2.length();
        
        int maksimum = 0;
        int poz_w1 = -1;
        int poz_w2 = -1;
        
        for (int i = 0; i < dl1 - maksimum; i++)
        {

            for (int k = dl2 - 1; k >= 0; k--)
            {
                int licznik = 0;
                int limit = Math.min(dl2, (dl1 -i + k) );  
                for (int j = k; j < limit; j++)
                {
                    if (tekst1.charAt(i+j-k) == tekst2.charAt(j))
                    {                        
                        licznik++;
                       
                        if (maksimum < licznik) 
                        {
                            maksimum = licznik;
                            poz_w1 = i + j - k - maksimum + 1;
                            poz_w2 = j - maksimum + 1;
                        }
                    }
                    else licznik = 0;
                }
            }
        }
        
        System.out.println("Poz w tekst1: " + poz_w1 + ", poz w tekst2: " + poz_w2 + ", dlugosc: " + maksimum);
        

                        
        System.out.println(tekst1.substring(0, pozycja_w1) + "\u001B[31m" 
                + tekst1.substring(poz_w1, maksimum + poz_w1) + "\u001B[0m" + tekst1.substring(maksimum + poz_w1) );
        System.out.println(tekst2.substring(0, poz_w2) + "\u001B[31m" 
                + tekst2.substring(poz_w2, maksimum + poz_w2) + "\u001B[0m" + tekst2.substring(maksimum + poz_w2) );
    }
    
}

Oraz to :

import java.util.Arrays;

public class Main {


    public static String[] substring(String s1, String s2){


        int[][] tab = new int[Math.max(s1.length(),s2.length())+1][Math.max(s1.length(),s2.length())+1];




        for(int i = 0; i <= s1.length(); i++){
            for(int j = 0; j <= s2.length(); j++){
                tab[i][j] = 0;
            }
        }

        String[] lista = new String[Math.max(s1.length(),s2.length())+1];

        for(int i = 0; i <= s1.length(); i++){
            for(int j = 0; j <= s2.length(); j++){
                if (i == 0 || j == 0){
                    tab[i][j] = 0;
                } else {
                    if(s1.charAt(i-1) == s2.charAt(j-1)){
                        tab[i][j] = tab[i-1][j-1]+1;
                    }
                    int x = 0;
                    while (tab[i-x][j-x] > 0){
                        lista[x] = s1.substring(i-tab[i][j]+x, i);
                        x++;
                    }
                }
            }
        }

        return lista;
    }


    public static void main(String[] args) {


        System.out.println(Arrays.toString(substring("ABAABBAAABBBA","AAABAABBABABA")));


    } // main
}

Jeden wypisuje tylko najdłuższy, a drugi wypisuje tylko kilka wspólnych.
Wiemy, że nie tędy droga, żeby ktoś to za nas napisał. Natomiast chociaż jakaś podpowiedź, co można zrobić od czego zacząć :p

Napisałem coś takiego w JavaScripcie. Nie wiem, czy dobrze, ale wydaje się działać. Może posłużyć jako pseudokod.

Implementacja

function allCommonSubstrings(s1, s2) {
    // Find all common substrings (will NOT include duplicates)
    const uniqueResult = new Set();
    for (let i = 0; i < s1.length; ++i) {
        for (let k = 0; k < s1.length; ++k) {
            if (i !== k) { // substrings of zero length makes no sense in our case
                const substring = s1.slice(i, k + 1); // k + 1 because slice() works that way
                if (substring.length > 1 && s2.includes(substring)) {
                    uniqueResult.add(substring);
                }
            }
        }
    }

    // Sort (must go before checking substrings of substrings)
    // The function sort() works in place (i.e. modifies the array)
    const sortedUniqueResult = new Array(...uniqueResult).sort((elem1, elem2) => {
        if (elem1.length === elem2.length) {
            // A group of elements in which all have the same length
            return elem1.localeCompare(elem2); // sort alphabetically
        }
        // Warning: in JavaScript, false is 0 and true is 1
        return elem1.length < elem2.length; // sort from longer to shorter elements
    });

    // Remove all substrings that are in some other substring
    const nonrepeatingSortedUniqueResult = new Array();
    nonrepeatingSortedUniqueResult.push(sortedUniqueResult[0]); // add the longest substring
    for (let i = 0; i < nonrepeatingSortedUniqueResult.length; ++i) {
        for (let k = 0; k < sortedUniqueResult.length; ++k) {
            // Comparing a string to itself makes no sense,
            //  as well as searching for longer one in a shorter one
            if (i !== k &&
                nonrepeatingSortedUniqueResult[i].length > sortedUniqueResult[k].length) {
                if (!nonrepeatingSortedUniqueResult[i].includes(sortedUniqueResult[k])) {
                    nonrepeatingSortedUniqueResult.push(sortedUniqueResult[k]);
                }
            }
        }
    }

    return nonrepeatingSortedUniqueResult;
}

Prosty test

console.log(allCommonSubstrings("ACCEEE", "CCBBBEEE"));

Test bardziej złożony

(mam nadzieję, że nie ma w nim błędu)

function testAllCommonSubstrings(a, b, expectedResult) {
    const actualResult = allCommonSubstrings(a, b);
    if (expectedResult.length !== actualResult.length) {
        return false; // to avoid comparing later with non-existing elements
    }
    for (let i = 0; i < expectedResult.length; ++i) {
        // Remember: in JavaScript, false is 0 and true is 1
        if (expectedResult[i].localeCompare(actualResult[i])) {
            return false;
        }
    }
    return true;
}

// Data comes in the form: string1, string2, expected result
// Warning: the order of expected result elements matters
const testData = [
    ["ACCEEE", "CCBBBEEE", ["EEE", "CC"]],
    ["DADKKK", "KDADL", ["DAD"]]
    // here you can make further test cases
];

testData.forEach(elem => {
    console.log("Testing function for strings " + elem[0] + " and " + elem[1]);
    console.log(testAllCommonSubstrings(...elem));
});

Tutaj na żywo działanie: https://jsfiddle.net/vudL1eks/12/

UPDATE: Mój błąd, powyższy kod zachowuje kolejność wstawiania podciągów, nie zachowuje tylko samych duplikatów.

UPDATE2: Dodałem ograniczenie na znaki i sortowanie.

UPDATE3: Kod jest maksymalnie nieefektywny, na pewno da się napisać coś lepszego, no, ale nie wiem, czy będzie tak czytelne. ;)

UPDATE4: Zgodnie z informacjami w komentarzu poniżej (Wypisywanie części wspólnej z dwóch słów.), obecnie ten przykład jest błędny, ale postaram się go poprawić.

UPDATE5:

Zaktualizowałem kod względem komentarzy pod postem poniżej (Wypisywanie części wspólnej z dwóch słów.). Dodałem testy (mam nadzieję, że działają poprawne). Oczywiście kod nadal jest maksymalnie nieefektywny (a może nawet bardziej niż był).

Starałem się go rozpisać, żeby było bardziej czytelnie, ale nie wiem, czy mi wyszło. Starałem się unikać np. funkcji takich jak splice czy też dodatkowych ifów.

"Części wspólne" można różnie zdefiniować, np. jako trójkę (x, y, z), gdzie z to powtarzający się substring, a x i y to jego pozycja odpowiednio w pierwszym i drugim słowie.
Zakładając, że chodzi jedynie o zbiór powtarzających się podciągów, to proponuję stworzyć metodę, która dla wejściowego stringa zwróci zbiór wszystkich jego substringów, wywołać ją dla obu słów i wziąć część wspólną z obu zbiorów.

Iteruj po pierwszym ciągu po ileś tam znaków od początku do końca i sprawdzaj czy drugi ciąg to zawiera. Jak dojdziesz do końca to zwiększ ilość znaków. Wyniki wrzucaj do setu by nie było duplikatów. Skorzystaj z klasy StringBuilder. Tam masz na pewno metodę contains(String) ( może w zwykłej klasie String też jest ).

Nie wiem jakie wasz nauczyciel ma podejście do korzystania z bibliotek, ale wydaje mi się, że to będzie znacznie prostsze :)

Pseudokod (Python), przepisanie do Javy będzie trywialne. Można to nazwać rozwiązaniem naiwnym - sprawdza czy co najmniej dwuelementowa kombinacja pierwszego ciągu jest substringiem drugiego. Złożoność nierewelacyjna O(n^3), ale na razie nie widzę lepszej:

def comb(str1, str2, out, ind):
	for i in range(ind, len(str1)): # for i = ind to str1.length() - 1
		str2 += str1[i]
		if len(str2) > 1: # str2.length()
			out.append(str2)
		comb(str1, str2, out, i + 1)
		str2 = str2.replace(str2[len(str2) - 1], "") # deleteCharAt(str2.length() - 1)
	return out

def common_substrings(str1, str2):
	out = []
	for token in comb(str1, "", [], 0): # for (String token: comb(str1, "", [], 0))
		if token in str2: # if token is substring of str2
			out.append(token)
	return out

print(common_substrings("AABABB", "BAABAB")) # -> ['AA', 'AAB', 'AABA', 'AABAB', 'BA', 'BAB', 'AB', 'AB', 'AB', 
# 'AB', 'ABA', 'ABAB', 'AAB', 'AA', 'AAB', 'AAB', 'BA', 'BAB', 'AB', 'AB', 'AB']
		

Można się wzorować rozwiazaniu używajacym programowania dynamicznego: https://stackoverflow.com/a/34807141 . W tym przykładzie, w macierzy pomocniczej liczba w komórce [i][j] oznacza długość wspólnego podciagu który kończy się na pozycji i w pierwszym i j w drugim słowie. Można lekko przerobić ten przykład, żeby zamiast śledzić największa długość, na bieżaco dodawać nowo odkryte wspólne części do kolekcji, która będzie utrzymywała porzadek po długości. Teraz wystarczy przeiterować po otrzymanej kolekcji i przy każdym elemencie wyrzucić pozostałe elementy które przecinaja się z właśnie "użytym". Wyszło mi coś takiego, za błędy nie odpowiadam:

	static Set<String> solve(String first, String second) {
		int[][] table = new int[first.length()][second.length()];
		Set<String> result = new HashSet<>();
		TreeSet<CommonPart> candidates = new TreeSet<>(((Comparator<CommonPart>) (a, b) -> {
			if (a.length != b.length) return Integer.compare(a.length, b.length);
			if (a.start == b.start) return 0;
			return -1;
		}).reversed());
		for (int i = 0; i < first.length(); i++) {
			for (int j = 0; j < second.length(); j++) {
				if (first.charAt(i) != second.charAt(j)) {
					continue;
				}
				int length = table[i][j] = (i == 0 || j == 0) ? 1 : 1 + table[i - 1][j - 1];
				if (length >= 2) {
					candidates.add(new CommonPart(i, length));
				}
			}
		}
		while (!candidates.isEmpty()) {
			CommonPart longest = candidates.first();
			result.add(longest.substring(first));
			candidates.removeIf(longest::overlaps);
		}
		return result;
	}
	
	static class CommonPart {
		int start;
		int end;
		int length;
		CommonPart(int position, int length) {
			this.start = position - length + 1;
			this.end = start + length;
			this.length = length;
		}
		String substring(String from) {
			return from.substring(start, end);
		}
		boolean overlaps(CommonPart other) {
			return start < other.end && other.start < end;
		}
	}