1 import java.util.*;
   2 
   3 public class EserciziSuStringhe {
   4 
   5 	public static void scambiaElementi (String v[], int i, int j) {
   6 		String temp = v[i];
   7 		v[i] = v[j];
   8 		v[j] = temp;
   9 	}
  10 
  11 	public static void bubbleSort ( String a[] ) {
  12 		boolean scambi = true;
  13 		int border = a.length - 1;
  14 		while ( scambi && border > 0 ) {
  15 			scambi = false;
  16 			for ( int j = 0; j < border; j++) {
  17 				if (a[j].compareTo(a[j+1]) > 0) {
  18 					scambiaElementi(a,j,j+1);
  19 					scambi = true;
  20 				}
  21 			}
  22 			border--;
  23 		}
  24 	}
  25 	
  26 	public static String eliminaSpaziEstremi(String s){
  27 		int i=0, f=s.length()-1;
  28 		
  29 		while(s.charAt(i)==' ' && i<s.length())
  30 			i++;
  31 		while(s.charAt(f)==' ' && f>=0)
  32 			f--;
  33 
  34 		String ris="";
  35 		for(int k=i; k<=f; k++)
  36 			ris += s.charAt(k);
  37 		return ris;
  38 		
  39 //		In alternativa:
  40 //		return s.substring(i, f+1);
  41 	}
  42 	
  43 	public static String eliminaSpazi(String s){
  44 		String ris="";
  45 		for(int i=0; i<s.length(); i++)
  46 			if(s.charAt(i)!=' ')
  47 				ris += s.charAt(i);
  48 		return ris;
  49 	}
  50 	
  51 	public static String eliminaSpaziRipetuti(String s){
  52 		String ris="";
  53 		int i=0;
  54 
  55 		while(i<s.length()){
  56 			ris += s.charAt(i);
  57 			if(s.charAt(i)==' ')
  58 				while(i<s.length() && s.charAt(i)==' ')
  59 					i++;
  60 			else
  61 				i++;
  62 		}
  63 		return ris;
  64 	}
  65 	
  66 	public static int ricercaBinariaIterativa(String[] v, String elem){
  67 	    int min = 0;
  68 	    int max = v.length-1;
  69 	    int mezzo = (max+min)/2;
  70 	    boolean trovato = false;
  71 	    while(!trovato && min <= max) {
  72 	        mezzo = (max+min)/2;
  73 	        if(v[mezzo].equals(elem)) 
  74 	        	trovato=true; 
  75 	        if(v[mezzo].compareTo(elem) < 0) 
  76 	        	min = mezzo + 1;
  77 	        else max = mezzo - 1;
  78 	    }
  79 	    if(trovato) 
  80 	    	return mezzo;
  81 	    return -1;
  82 	}
  83 	
  84 	public static int ricercaBinariaRicorsiva (String v[], String elem, int inf, int sup) {
  85 		if( sup < inf )
  86 			return -1;
  87 	
  88 		int med = (inf + sup)/2;
  89 		if (elem.equals(v[med]))
  90 			return med;
  91 		if (elem.compareTo(v[med]) < 0)
  92 			return ricercaBinariaRicorsiva(v, elem, inf, med-1);
  93 		return ricercaBinariaRicorsiva(v, elem, med+1, sup);
  94 	}
  95 
  96 	public static void main(String[] args) {
  97 		Scanner input = new Scanner(System.in); 
  98 
  99 		System.out.println("Inserisci una frase:");
 100 		String frase = input.nextLine();
 101 		
 102 		String fraseSenzaSpaziEstremi = eliminaSpaziEstremi(frase);
 103 		System.out.println("La tua frase senza gli spazi iniziali e finali:");
 104 		System.out.println(fraseSenzaSpaziEstremi);
 105 		System.out.println("Risultato ottenuto con trim:");
 106 		System.out.println(frase.trim());
 107 		
 108 		String fraseSenzaSpazi = eliminaSpazi(frase);
 109 		System.out.println("La tua frase senza nessuno spazio:");
 110 		System.out.println(fraseSenzaSpazi);
 111 		System.out.println("Risultato ottenuto con replaceAll:");
 112 		System.out.println(frase.replaceAll(" ", ""));
 113 		
 114 		String fraseSenzaSpaziRipetuti = eliminaSpaziRipetuti(frase);
 115 		System.out.println("La tua frase con non più di uno spazio di seguito:");
 116 		System.out.println(fraseSenzaSpaziRipetuti);
 117 		
 118 		// Ottieni array di parole
 119 		String[] parole = eliminaSpaziRipetuti(frase.trim()).split(" ");
 120 		// Ordina l'array
 121 		bubbleSort(parole);
 122 		// Stampa frase ordinata
 123 		System.out.println("Frase con parole in ordine lessicografico:");
 124 		String fraseOrdinata = "";
 125 		for(int i=0; i<parole.length; i++)
 126 			fraseOrdinata += (parole[i] + " ");
 127 		System.out.println(fraseOrdinata);
 128 		// Cerca parola
 129 		System.out.println("Parola da cercare:");
 130 		String parola = input.next();
 131 //		int posizione = ricercaBinariaIterativa(parole, parola);
 132 		int posizione = ricercaBinariaRicorsiva(parole, parola, 0, parole.length -1);
 133 		if(posizione >= 0)
 134 			System.out.println("La parola " + parola + " compare in posizione " + (posizione+1));
 135 		else
 136 			System.out.println("La parola " + parola + " non compare nella frase");
 137 			
 138 	}
 139 
 140 }