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 
  41 //		return s.substring(i, f+1);
  42 	}
  43 	
  44 	public static String eliminaSpazi(String s){
  45 		String ris="";
  46 		for(int i=0; i<s.length(); i++)
  47 			if(s.charAt(i)!=' ')
  48 				ris += s.charAt(i);
  49 		return ris;
  50 	}
  51 	
  52 	public static String eliminaSpaziRipetuti(String s){
  53 		String ris="";
  54 		int i=0;
  55 
  56 		while(i<s.length()){
  57 			ris += s.charAt(i);
  58 			if(s.charAt(i)==' ')
  59 				while(i<s.length() && s.charAt(i)==' ')
  60 					i++;
  61 			else
  62 				i++;
  63 		}
  64 		return ris;
  65 	}
  66 	
  67 	public static int ricercaBinariaIterativa(String[] v, String elem){
  68 	    int min = 0;
  69 	    int max = v.length-1;
  70 	    int mezzo = (max+min)/2;
  71 	    boolean trovato = false;
  72 	    while(!trovato && min <= max) {
  73 	        mezzo = (max+min)/2;
  74 	        if(v[mezzo].equals(elem)) 
  75 	        	trovato=true; 
  76 	        if(v[mezzo].compareTo(elem) < 0) 
  77 	        	min = mezzo + 1;
  78 	        else max = mezzo - 1;
  79 	    }
  80 	    if(trovato) 
  81 	    	return mezzo;
  82 	    return -1;
  83 	}
  84 	
  85 	public static int ricercaBinariaRicorsiva (String v[], String elem, int inf, int sup) {
  86 		if( sup < inf )
  87 			return -1;
  88 	
  89 		int med = (inf + sup)/2;
  90 		if (elem.equals(v[med]))
  91 			return med;
  92 		if (elem.compareTo(v[med]) < 0)
  93 			return ricercaBinariaRicorsiva(v, elem, inf, med-1);
  94 		return ricercaBinariaRicorsiva(v, elem, med+1, sup);
  95 	}
  96 
  97 	public static void main(String[] args) {
  98 		Scanner input = new Scanner(System.in); 
  99 
 100 		System.out.println("Inserisci una frase:");
 101 		String frase = input.nextLine();
 102 		
 103 		String fraseSenzaSpaziEstremi = eliminaSpaziEstremi(frase);
 104 		System.out.println("La tua frase senza gli spazi iniziali e finali:");
 105 		System.out.println(fraseSenzaSpaziEstremi);
 106 		System.out.println("Risultato ottenuto con trim:");
 107 		System.out.println(frase.trim());
 108 		
 109 		String fraseSenzaSpazi = eliminaSpazi(frase);
 110 		System.out.println("La tua frase senza nessuno spazio:");
 111 		System.out.println(fraseSenzaSpazi);
 112 		System.out.println("Risultato ottenuto con replaceAll:");
 113 		System.out.println(frase.replaceAll(" ", ""));
 114 		
 115 		String fraseSenzaSpaziRipetuti = eliminaSpaziRipetuti(frase);
 116 		System.out.println("La tua frase con non più di uno spazio di seguito:");
 117 		System.out.println(fraseSenzaSpaziRipetuti);
 118 		
 119 		// Ottieni array di parole
 120 		String[] parole = eliminaSpaziRipetuti(frase.trim()).split(" ");
 121 		// Ordina l'array
 122 		bubbleSort(parole);
 123 		// Stampa frase ordinata
 124 		System.out.println("Frase con parole in ordine lessicografico:");
 125 		String fraseOrdinata = "";
 126 		for(int i=0; i<parole.length; i++)
 127 			fraseOrdinata += (parole[i] + " ");
 128 		System.out.println(fraseOrdinata);
 129 		// Cerca parola
 130 		System.out.println("Parola da cercare:");
 131 		String parola = input.next();
 132 //		int posizione = ricercaBinariaIterativa(parole, parola);
 133 		int posizione = ricercaBinariaRicorsiva(parole, parola, 0, parole.length -1);
 134 		if(posizione >= 0)
 135 			System.out.println("La parola " + parola + " compare in posizione " + (posizione+1));
 136 		else
 137 			System.out.println("La parola " + parola + " non compare nella frase");
 138 			
 139 	}
 140 
 141 }