Avendo la stringa di riferimento potresti creare una tabella temporanea che, ad esempio, ha come riferimento "Rossi" e prenda come elementi tutte i cognomi di lunghezza 5 e che cominciano con R in modo tale da scremare. Nella tabella poi potresti anche cominciare ad assegnare il valore di similarità dividendo gli elementi in "Rxxxx","Roxxx","Rosxx","Rossx","Rossi". Per la ricerca userei 3 thread che ricerchi 3 settori ben definiti della tabella.