Problema creazione landscape

gascas11

il 22 lug 2021, 19:07

14 risposte

gascas11

Pochi posts

Iscritto da: apr, 2021

Messaggi:: 22

Problema creazione landscape

22 lug 2021, 19:21

Ciao a tutti, ho creato una metodo in java che prese a parametro due stringhe (testo, pattern) tramite suffix automa mi stampa il numero di occorrenze del pattern nel testo; il metodo funziona perfettamente e da gli output corretti.
Ora dovrei creare un metodo che prese a parametro sempre le due stringhe mi stampi il landscape delle stesse (ossia una matrice bidimensionale, che rappresenta il numero di volte in cui le sottostringhe della stringa di destinazione si verificano in una stringa di origine).
Non riesco a creare questa matrice bidimensionale che deve avere nella prima riga i valori delle occorrenze delle sottostringhe di lunghezza 1, nella seconda riga i valori delle occorrenze delle sottostringhe di lunghezza 2 fino ad arrivare in cima all'intera sottostringa.
Posto il codice

Qualcuno mi può aiutare?

 
 public static void generateLandscape(String sequence1, String sequence2) {
    	    	
    	int d = 0;
    	String c = null;
    	int start = 0;
    	//Estraggo fattori di lunghezza 1
    	for(int i = 1; i<=sequence2.length();i++) {
    	c = sequence2.substring(start, i);
    	start = start +1;
    	System.out.println(c);
    	
    	d=printAllPositionsOfOccur1(sequence1, c);
    	
        System.out.println(d);
    	
   }

Dentro il ciclo for il medoto printAllPositionsOfOccur1(sequence1, c) mi stampa i valori delle occorrenze sbagliati (come se li sommasse tutti) In allegato l'output che vorrei ottenere

14 Risposte

Weierstrass

Utente Famoso

Iscritto da: feb, 2019

Messaggi:: 2248

Re: Problema creazione landscape

23 lug 2021, 00:10


package landscape;

public class Landscape {
    
    public static int[][] generateLandscape(String sequence){
        int land[][] = new int[sequence.length()][sequence.length()];
        int i, j, k, l;
        for(i = 1; i <= sequence.length(); i++)          
            for(j = 0; j <= sequence.length() - i; j++)
                for(k = 0; k <= sequence.length() - i; k++){
                    for(l = 0; l < i; l++)
                        if(sequence.charAt(j + l) != sequence.charAt(k + l))
                            break;    
                    if(l == i)
                        land[sequence.length() - i][i + j - 1]++;
                }
        return land;        
    }    

    public static void main(String[] args) {
        String test = "GTAGTAAAC";
        int matrix[][] = generateLandscape(test);
        for(int i = 0; i < test.length(); i++){
            for(int j = 0; j < test.length(); j++)
                if(matrix[i][j] > 9)
                    System.out.print('+');
                else if(matrix[i][j] == 0)
                    System.out.print(' ');
                else
                    System.out.print(matrix[i][j]);
            System.out.println();
        }
        System.out.println(test);
    }
    
}

G
gascas11
Pochi posts
Iscritto da
apr, 2021
Messaggi:
22
Re: Problema creazione landscape
23 lug 2021, 11:08
Grazie mille!

gascas11

Pochi posts

Iscritto da: apr, 2021

Messaggi:: 22

Re: Problema creazione landscape

23 lug 2021, 11:23

Innanzitutto grazie per la tua disponibilità; il mio problema è che per generare il landscape dovrei utilizzare il metodo printAllPositionsOfOccur(String s1, String s2) che ho creato che va a stampare le occorrenze della stringa s2 in s1..quindi il landscape a parametro dovrebbe prendere 2 stringhe, una di origine e una stringa pattern di cui dovrei andare a calcolare le occorrenze di tutte le sottostringhe dalla dimensione 1 fino alla lunghezza della stringa.
Questo perchè devo utlizzare per forza di cose un suffix automaton.
Come posso procedere?


Import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;

public class SuffixAutomaton {
    public static State[] suffixAutoma;   //suffix Automa
    public static int curSize, last;    //dimensione corrente e ultima
    public static HashSet<Integer> res = new HashSet<>(); //Risultato della ricerca delle posizioni delle occorrenze

    public static class State {
        int len, link;
        HashMap<Character, Integer> next = new HashMap<>();  //elenco di transizioni o archi

        boolean is_clon;
        int first_pos;
        ArrayList<Integer> inv_link = new ArrayList<>();

        public State() {
        }

    };

   
    // inizializza il suffix automa (crea un suffix automa con un singolo stato)
    public static void suffAutomat_Init() {
        curSize = last = 0;
        if (suffixAutoma[0] == null) {
            suffixAutoma[0] = new State();
        }
        suffixAutoma[0].len = 0;
        suffixAutoma[0].link = -1;
        ++curSize;

    }

    //aggiunge il carattere successivo alla fine della riga corrente, ricostruendo l'automa di conseguenza
    public static void suffAutomat_Extend(char c) {
        int cur = curSize++;
        if (suffixAutoma[cur] == null) {
            suffixAutoma[cur] = new State();
        }
        suffixAutoma[cur].first_pos = suffixAutoma[last].len - 1;
        suffixAutoma[cur].len = suffixAutoma[last].len + 1;
        int p;
        for (p = last; p != -1 && !suffixAutoma[p].next.containsKey(c); p = suffixAutoma[p].link) {
            suffixAutoma[p].next.put(c, cur);
        }

        if (p == -1) {
            suffixAutoma[cur].link = 0;
        } else {
            int q = suffixAutoma[p].next.get(c);
            if (suffixAutoma[p].len + 1 == suffixAutoma[q].len) {
                suffixAutoma[cur].link = q;
            } else {
                int clone = curSize++;
                if (suffixAutoma[clone] == null) {
                    suffixAutoma[clone] = new State();
                }
                suffixAutoma[clone].is_clon = true;
                suffixAutoma[clone].len = suffixAutoma[p].len + 1;
                suffixAutoma[clone].next.putAll(suffixAutoma[q].next);
                suffixAutoma[clone].link = suffixAutoma[q].link;
                suffixAutoma[clone].first_pos = suffixAutoma[q].first_pos;
                for (; p != -1 && suffixAutoma[p].next.get(c) == q; p = suffixAutoma[p].link) {
                    suffixAutoma[p].next.remove(c);
                    suffixAutoma[p].next.put(c, clone);
                }
                suffixAutoma[q].link = suffixAutoma[cur].link = clone;
            }
        }
        last = cur;
    }

    //Stampa tutte le posizioni delle occorrenza di s2 in s1
    public static void printAllPositionsOfOccur(String s1, String s2){
        suffixAutoma = new State[(2 * s1.length())];
        suffAutomat_Init();
        for (int i = 0; i < s1.length(); i++) {
            suffAutomat_Extend(s1.charAt(i));
        }
        for (int v = 1; v < curSize; ++v) {
            suffixAutoma[suffixAutoma[v].link].inv_link.add(v);
        }
        State elem = suffixAutoma[0];
        int a = 0;
        for (int i = 0; i < s2.length(); i++) {
            if (elem.next.containsKey(s2.charAt(i))) {
                a = elem.next.get(s2.charAt(i));
                elem = suffixAutoma[a];
            } else {
                a = -1;
                break;
            }
        }
        if (a != -1) {
            output_all_occurences(a, s2.length());
        }
        System.out.println("Numero di occorrenze: "+ res.size());
        if (res.size() == 0){
            return;
        }
        int n = res.size();
        Integer[] b;
        b = res.toArray(new Integer[n]);
        Arrays.sort(b);
        System.out.println("Posizione delle occorrenze: ");
        for (int i = 0; i < n; i++) {
            System.out.print(b[i] + " ");
        }
    }

    
    public static void output_all_occurences(int v, int P_length) {
        if (!suffixAutoma[v].is_clon) {
            res.add(suffixAutoma[v].first_pos - P_length + 2);
        }
        for (int i = 0; i < suffixAutoma[v].inv_link.size(); ++i) {
            output_all_occurences(suffixAutoma[v].inv_link.get(i), P_length);
        }
    }

   public static void main(String[] args) throws IOException {
        String testo = "GTAGTAAAC";
        String pattern = "GTAGTAAAC";

        printAllPositionsOfOccur(testo, pattern);
        
     
   }

Weierstrass
Utente Famoso
Iscritto da
feb, 2019
Messaggi:
2248
Re: Problema creazione landscape
23 lug 2021, 11:32
Fai l'esempio pratico con due stringhe diverse e il risultato che ti aspetti. Nell'esempio hai messo una stringa sola

Weierstrass

Utente Famoso

Iscritto da: feb, 2019

Messaggi:: 2248

Re: Problema creazione landscape

23 lug 2021, 12:30

Comunque, non se ho capito male (in mancanza dell'esempio)


package landscape;

public class Landscape {
    
    public static int[][] generateLandscape(String sequence, String pattern){
        int land[][] = new int[pattern.length()][pattern.length()];
        int i, j, k, l;
        for(i = 1; i <= pattern.length(); i++)          
            for(j = 0; j <= pattern.length() - i; j++)
                for(k = 0; k <= sequence.length() - i; k++){
                    for(l = 0; l < i; l++)
                        if(pattern.charAt(j + l) != sequence.charAt(k + l))
                            break;    
                    if(l == i)
                        land[pattern.length() - i][i + j - 1]++;
                }
        return land;        
    }    
    
    public static void printLandscape(int[][] landscape){
        for(int i = 0; i < landscape[0].length; i++){
            for(int j = 0; j < landscape[0].length; j++)
                if(landscape[i][j] > 9)
                    System.out.print('+');
                else if(landscape[i][j] == 0)
                    System.out.print(' ');
                else
                    System.out.print(landscape[i][j]);
            System.out.println();
        }       
    }    

    public static void main(String[] args) {
        String test_seq = "GTAGTAGTAGTA";        
        String test_pat = "GTAGTAAAC";
        System.out.println(test_seq);        
        int matrix[][] = generateLandscape(test_seq, test_pat);
        printLandscape(matrix);
        System.out.println(test_pat);
        System.out.println();
        test_seq = "GTA";        
        test_pat = "GTAGTAAAC";
        System.out.println(test_seq);        
        matrix = generateLandscape(test_seq, test_pat);
        printLandscape(matrix);
        System.out.println(test_pat);      
        System.out.println();
        test_seq = "GTAGTAAAC";        
        test_pat = "GTAGTAAAC";
        System.out.println(test_seq);        
        matrix = generateLandscape(test_seq, test_pat);
        printLandscape(matrix);
        System.out.println(test_pat);           
    }
    
}

gascas11

Pochi posts

Iscritto da: apr, 2021

Messaggi:: 22

Re: Problema creazione landscape

23 lug 2021, 13:07

Si esattamente è l'output che devo ottenere..funziona con tutti gli esempi.
Ultimo problema che è rimasto, è che per contare il numero delle occorrenze dovrei utilizzare i metodi che ho creato con i suffix automa, ossia questi


//Stampa tutte le posizioni delle occorrenza di s2 in s1
    public static void printNumberOfOccur(String s1, String s2){
        suffixAutoma = new State[(2 * s1.length())];
        suffAutomat_Init();
        for (int i = 0; i < s1.length(); i++) {
            suffAutomat_Extend(s1.charAt(i));
        }
        for (int v = 1; v < curSize; ++v) {
            suffixAutoma[suffixAutoma[v].link].inv_link.add(v);
        }
        State elem = suffixAutoma[0];
        int a = 0;
        for (int i = 0; i < s2.length(); i++) {
            if (elem.next.containsKey(s2.charAt(i))) {
                a = elem.next.get(s2.charAt(i));
                elem = suffixAutoma[a];
            } else {
                a = -1;
                break;
            }
        }
        if (a != -1) {
            output_all_occurences(a, s2.length());
        }
        System.out.println("Numero di occorrenze: "+ res.size());
        if (res.size() == 0){
            return;
        }
    
    }

    
    public static void output_all_occurences(int v, int P_length) {
        if (!suffixAutoma[v].is_clon) {
            res.add(suffixAutoma[v].first_pos - P_length + 2);
        }
        for (int i = 0; i < suffixAutoma[v].inv_link.size(); ++i) {
            output_all_occurences(suffixAutoma[v].inv_link.get(i), P_length);
        }
    }

Come procedo?

G
gascas11
Pochi posts
Iscritto da
apr, 2021
Messaggi:
22
Re: Problema creazione landscape
23 lug 2021, 13:09
Praticamente il metodo stampa il numero di occorrenze della stringa s2 presenti in s1 utilizzando i suffix automa.
Tramite questi dovrei creare il landscape

gascas11

Pochi posts

Iscritto da: apr, 2021

Messaggi:: 22

Re: Problema creazione landscape

23 lug 2021, 15:12

Questo è il codice completo che ho creato ..




import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;

public class SuffixAutomaton {
    public static State[] suffixAutoma;   //suffix Automa
    public static int curSize, last;    //dimensione corrente e ultima
    public static HashSet<Integer> res = new HashSet<>(); //Risultato della ricerca delle posizioni delle occorrenze

    public static class State {
        int len, link;
        HashMap<Character, Integer> next = new HashMap<>();  //elenco di transizioni o archi

        boolean is_clon;
        int first_pos;
        ArrayList<Integer> inv_link = new ArrayList<>();

        public State() {
        }

    };

   
    // inizializza il suffix automa (crea un suffix automa con un singolo stato)
    public static void suffAutomat_Init() {
        curSize = last = 0;
        if (suffixAutoma[0] == null) {
            suffixAutoma[0] = new State();
        }
        suffixAutoma[0].len = 0;
        suffixAutoma[0].link = -1;
        ++curSize;

    }

    //aggiunge il carattere successivo alla fine della riga corrente, ricostruendo l'automa di conseguenza
    public static void suffAutomat_Extend(char c) {
        int cur = curSize++;
        if (suffixAutoma[cur] == null) {
            suffixAutoma[cur] = new State();
        }
        suffixAutoma[cur].first_pos = suffixAutoma[last].len - 1;
        suffixAutoma[cur].len = suffixAutoma[last].len + 1;
        int p;
        for (p = last; p != -1 && !suffixAutoma[p].next.containsKey(c); p = suffixAutoma[p].link) {
            suffixAutoma[p].next.put(c, cur);
        }

        if (p == -1) {
            suffixAutoma[cur].link = 0;
        } else {
            int q = suffixAutoma[p].next.get(c);
            if (suffixAutoma[p].len + 1 == suffixAutoma[q].len) {
                suffixAutoma[cur].link = q;
            } else {
                int clone = curSize++;
                if (suffixAutoma[clone] == null) {
                    suffixAutoma[clone] = new State();
                }
                suffixAutoma[clone].is_clon = true;
                suffixAutoma[clone].len = suffixAutoma[p].len + 1;
                suffixAutoma[clone].next.putAll(suffixAutoma[q].next);
                suffixAutoma[clone].link = suffixAutoma[q].link;
                suffixAutoma[clone].first_pos = suffixAutoma[q].first_pos;
                for (; p != -1 && suffixAutoma[p].next.get(c) == q; p = suffixAutoma[p].link) {
                    suffixAutoma[p].next.remove(c);
                    suffixAutoma[p].next.put(c, clone);
                }
                suffixAutoma[q].link = suffixAutoma[cur].link = clone;
            }
        }
        last = cur;
    }

    //Stampa tutte le posizioni delle occorrenza di s2 in s1
    public static void printAllPositionsOfOccur(String s1, String s2){
        suffixAutoma = new State[(2 * s1.length())];
        suffAutomat_Init();
        for (int i = 0; i < s1.length(); i++) {
            suffAutomat_Extend(s1.charAt(i));
        }
        for (int v = 1; v < curSize; ++v) {
            suffixAutoma[suffixAutoma[v].link].inv_link.add(v);
        }
        State elem = suffixAutoma[0];
        int a = 0;
        for (int i = 0; i < s2.length(); i++) {
            if (elem.next.containsKey(s2.charAt(i))) {
                a = elem.next.get(s2.charAt(i));
                elem = suffixAutoma[a];
            } else {
                a = -1;
                break;
            }
        }
        if (a != -1) {
            output_all_occurences(a, s2.length());
        }
        System.out.println("Numero di occorrenze: "+ res.size());
        if (res.size() == 0){
            return;
        }
        int n = res.size();
        Integer[] b;
        b = res.toArray(new Integer[n]);
        Arrays.sort(b);
        System.out.println("Posizione delle occorrenze: ");
        for (int i = 0; i < n; i++) {
            System.out.print(b[i] + " ");
        }
    }

    
    public static void output_all_occurences(int v, int P_length) {
        if (!suffixAutoma[v].is_clon) {
            res.add(suffixAutoma[v].first_pos - P_length + 2);
        }
        for (int i = 0; i < suffixAutoma[v].inv_link.size(); ++i) {
            output_all_occurences(suffixAutoma[v].inv_link.get(i), P_length);
        }
    }

    //trova lcs
    public static String lcs(String S, String T){
        suffixAutoma = new State[(2 * S.length())];
        suffAutomat_Init();
        for (int i =0 ; i < S.length(); i++){
            suffAutomat_Extend(S.charAt(i));
        }
        int v = 0, l = 0, best = 0, bestpos=0;
        for (int i =0; i < T.length(); i++){
            while (v != 0 && !suffixAutoma[v].next.containsKey(T.charAt(i))){
                v = suffixAutoma[v].link;
                l = suffixAutoma[v].len;
            }
            if (suffixAutoma[v].next.containsKey(T.charAt(i))){
                v = suffixAutoma[v].next.get(T.charAt(i));
                l++;
            }
            if (l > best){
                best = l;
                bestpos = i;
            }
        }
        return T.substring(bestpos - best  +1, bestpos  +1 );
    }
    

    
    public static void main(String[] args) throws IOException {
        String testo = "GTAGTAAAC";
        String pattern = "GTA";

        printAllPositionsOfOccur(testo, pattern);
        System.out.println("\n");
        System.out.println("Pattern di riferimento: " + lcs(testo, pattern));
    
    }
}

Weierstrass

Utente Famoso

Iscritto da: feb, 2019

Messaggi:: 2248

Re: Problema creazione landscape

23 lug 2021, 16:02

Non ho idea di come funzioni un suffix automa.

Se vuoi vedere il dettaglio delle posizioni delle varie occorrenze, potresti fare ad esempio così


package landscape;

import java.util.ArrayList;

public class Landscape {
    public String Sequence;
    public String Pattern; 
    public ArrayList<Integer>[][] Occurrences;
    
    public void printLandscape(){
        System.out.println(Sequence);
        int i, j;
        for(i = 0; i < Occurrences[0].length; i++){
            for(j = 0; j < Occurrences[0].length; j++)
                if(Occurrences[i][j].size() > 9)
                    System.out.print('+');
                else if(Occurrences[i][j].size() == 0)
                    System.out.print(' ');
                else
                    System.out.print(Occurrences[i][j].size());
            for(j = 0; j < Sequence.length() - Pattern.length(); j++)
                System.out.print(' ');
            System.out.print(' ');
            for(j = 0; j < Occurrences[0].length; j++){
                System.out.print("( ");
                Occurrences[i][j].forEach(x -> System.out.print(String.valueOf(x + 1) + ' '));
                System.out.print(')');
            }
            System.out.println();
        }   
        System.out.println(Pattern);
    }    
    
    public static void main(String[] args) {
        Landscape land = new Landscape("GTAGTAGTAGTA", "GTAGTAAAC");
        land.printLandscape();
        System.out.println();
        land = new Landscape("GTA", "GTAGTAAAC");
        land.printLandscape();
        System.out.println();
        land = new Landscape("GTAGTAAAC", "GTAGTAAAC");
        land.printLandscape();
    }    
    
    public Landscape(String sequence, String pattern) {
        Sequence = sequence;
        Pattern = pattern;
        Occurrences = new ArrayList[pattern.length()][pattern.length()];
        int i, j, k, l;
        for(i = 0; i < pattern.length(); i++)          
            for(j = 0; j < pattern.length(); j++)
                Occurrences[i][j] = new ArrayList<>();
        for(i = 1; i <= pattern.length(); i++)          
            for(j = 0; j <= pattern.length() - i; j++)
                for(k = 0; k <= sequence.length() - i; k++){
                    for(l = 0; l < i; l++)
                        if(pattern.charAt(j + l) != sequence.charAt(k + l))
                            break;    
                    if(l == i)
                        Occurrences[pattern.length() - i][i + j - 1].add(k); 
        }
    }
        
}

Sta a te integrare nel tuo programma. Comunque mi sembrano problemi diversi: cosa importa come vengono create le stringhe con le funzioni che hai richiesto?

G
gascas11
Pochi posts
Iscritto da
apr, 2021
Messaggi:
22
Re: Problema creazione landscape
23 lug 2021, 19:44
Perchè putroppo è un lavoro di ricerca su un articolo scientifico e mi richiede di calcolare le occorrenze con DAWG o suffix automaton

gascas11

Pochi posts

Iscritto da: apr, 2021

Messaggi:: 22

Re: Problema creazione landscape

16 ago 2021, 17:47

Weierstrass potresti spiegarmi supergiu i controlli che fai per crearti il landscape che mi avevi mandato tempo fa?
Grazie!

 public static int[][] generateLandscape(String sequence, String pattern){
        int land[][] = new int[pattern.length()][pattern.length()];
        int i, j, k, l;
        for(i = 1; i <= pattern.length(); i++)          
            for(j = 0; j <= pattern.length() - i; j++)
                for(k = 0; k <= sequence.length() - i; k++){
                    for(l = 0; l < i; l++)
                        if(pattern.charAt(j + l) != sequence.charAt(k + l))
                            break;    
                    if(l == i)
                        land[pattern.length() - i][i + j - 1]++;
                }
        return land;        
    }

G
gascas11
Pochi posts
Iscritto da
apr, 2021
Messaggi:
22
Re: Problema creazione landscape
21 set 2021, 19:08
Ciao, sto ancora lavorando sempre al landscape.

Come posso stampare il landscape come mostrata in figura b ?
G
gascas11
Pochi posts
Iscritto da
apr, 2021
Messaggi:
22
Re: Problema creazione landscape
22 set 2021, 10:37
In particolare dovrei stampare il num_occ nella cella piu' alta, delle linee per il contorno e l'interno spazi vuoti

Weierstrass

Utente Famoso

Iscritto da: feb, 2019

Messaggi:: 2248

Re: Problema creazione landscape

23 set 2021, 00:24

gascas11 ha scritto:
Ciao, sto ancora lavorando sempre al landscape.

Come posso stampare il landscape come mostrata in figura b ?

1.png

Prova così (modifica del mio ultimo post)


package landscape;

import java.util.ArrayList;

public class Landscape {
    public String Sequence;
    public String Pattern; 
    public ArrayList<Integer>[][] Occurrences;
    
    public void printLandscape(){
        System.out.println(Sequence);
        int i, j;
        for(i = 0; i < Occurrences[0].length; i++){
            for(j = 0; j < Occurrences[0].length; j++)
                if(Occurrences[i][j].size() > 9)
                    System.out.print('+');
                else if(Occurrences[i][j].size() == 0)
                    System.out.print(' ');
                else
                    System.out.print(Occurrences[i][j].size());
            for(j = 0; j < Sequence.length() - Pattern.length(); j++)
                System.out.print(' ');
            System.out.print(' ');
            for(j = 0; j < Occurrences[0].length; j++){
                System.out.print("( ");
                Occurrences[i][j].forEach(x -> System.out.print(String.valueOf(x + 1) + ' '));
                System.out.print(')');
            }
            System.out.println();
        }   
        System.out.println(Pattern);
    }    
    
    public void printLandscapeTriangles(){
        System.out.println(Sequence);
        int i, j, k, l;
        int lines[][]  = new int[Occurrences[0].length][Occurrences[0].length];
        for(i = 0; i < Occurrences[0].length; i++)
            for(j = 0; j < Occurrences[0].length; j++)
                lines[i][j] = Occurrences[i][j].size();
        for(i = 0; i < Occurrences[0].length; i++)
            for(j = 0; j < Occurrences[0].length; j++)
                if(lines[i][j] > 0)
                    for(k = i + 1; k < Occurrences[0].length; k++){
                        if(lines[k][j] == lines[i][j])
                           lines[k][j] = -1;                          
                        for(l = j - 1; l > i + j - k; l--)
                           if(lines[k][l] == lines[i][j])
                              lines[k][l] = 0;   
                        if(lines[k][l] == lines[i][j])
                              lines[k][l] = -2;  
                    }
        for(i = 0; i < Occurrences[0].length; i++){
            for(j = 0; j < Occurrences[0].length; j++)
                if(lines[i][j] > 9)
                    System.out.print('+');
                else if(lines[i][j] == 0)
                    System.out.print(' ');
                else if(lines[i][j] == -1)
                    System.out.print('|');      
                else if(lines[i][j] == -2)
                    System.out.print('/');                   
                else
                    System.out.print(Occurrences[i][j].size());
            for(j = 0; j < Sequence.length() - Pattern.length(); j++)
                System.out.print(' ');
            System.out.print(' ');
            for(j = 0; j < Occurrences[0].length; j++){
                System.out.print("( ");
                Occurrences[i][j].forEach(x -> System.out.print(String.valueOf(x + 1) + ' '));
                System.out.print(')');
            }
            System.out.println();
        }   
        System.out.println(Pattern);
    }    
    
    public static void main(String[] args) {
        Landscape land = new Landscape("GTAGTAGTAGTA", "GTAGTAAAC");
        land.printLandscapeTriangles();
        System.out.println();
        land = new Landscape("GTA", "GTAGTAAAC");
        land.printLandscapeTriangles();
        System.out.println();
        land = new Landscape("GTAGTAAAC", "GTAGTAAAC");
        land.printLandscapeTriangles();
    }    
    
    public Landscape(String sequence, String pattern) {
        Sequence = sequence;
        Pattern = pattern;
        Occurrences = new ArrayList[pattern.length()][pattern.length()];
        int i, j, k, l;
        for(i = 0; i < pattern.length(); i++)          
            for(j = 0; j < pattern.length(); j++)
                Occurrences[i][j] = new ArrayList<>();
        for(i = 1; i <= pattern.length(); i++)          
            for(j = 0; j <= pattern.length() - i; j++)
                for(k = 0; k <= sequence.length() - i; k++){
                    for(l = 0; l < i; l++)
                        if(pattern.charAt(j + l) != sequence.charAt(k + l))
                            break;    
                    if(l == i)
                        Occurrences[pattern.length() - i][i + j - 1].add(k); 
        }
    }
        
}

Devi accedere o registrarti per scrivere nel forum

14 risposte