private List < Match > findBestCombination ( final String password , final List < Match > all_matches , final Map < Integer , Match > brute_force_matches ) throws TimeoutException { if ( configuration . getCombinationAlgorithmTimeout ( ) <= 0 ) { throw new TimeoutException ( "findBestCombination algorithm disabled." ) ; } // The start time of this algorithm, if we take too long, we must throw an exception long start_time = System . currentTimeMillis ( ) ; final Map < Match , List < Match > > non_intersecting_matches = new HashMap <> ( ) ; // Build lists of non-intersecting matches for each match which start at a higher index than the current match. for ( int i = 0 ; i < all_matches . size ( ) ; i ++ ) { Match match = all_matches . get ( i ) ; List < Match > forward_non_intersecting_matches = new ArrayList <> ( ) ; for ( int n = i + 1 ; n < all_matches . size ( ) ; n ++ ) { Match next_match = all_matches . get ( n ) ; if ( next_match . getStartIndex ( ) > match . getEndIndex ( ) && ! ( next_match . getStartIndex ( ) < match . getEndIndex ( ) && match . getStartIndex ( ) < next_match . getEndIndex ( ) ) ) { boolean to_add = true ; for ( Match non_intersecting_match : forward_non_intersecting_matches ) { if ( next_match . getStartIndex ( ) > non_intersecting_match . getEndIndex ( ) ) { to_add = false ; break ; } } if ( to_add ) { forward_non_intersecting_matches . add ( next_match ) ; } } } Collections . sort ( forward_non_intersecting_matches , comparator ) ; non_intersecting_matches . put ( match , forward_non_intersecting_matches ) ; } // Find all matches we should consider as a seed for the recursive function. // There is no need to start the function with a match that is half way through the password. List < Match > seed_matches = new ArrayList <> ( ) ; for ( Match match : all_matches ) { boolean seed = true ; for ( List < Match > match_list : non_intersecting_matches . values ( ) ) { for ( Match m : match_list ) { if ( m . equals ( match ) ) { seed = false ; } } } if ( seed ) { seed_matches . add ( match ) ; } } Collections . sort ( seed_matches , comparator ) ; // Run the recursive function for each seed, and the lowest entropy matches will be set with the best combination. for ( Match match : seed_matches ) { generateMatches ( start_time , password , match , non_intersecting_matches , brute_force_matches , new ArrayList < Match > ( ) , 0 ) ; } Collections . sort ( best_matches , comparator ) ; return best_matches ; }
Finds the most optimal matches by recursively building out every combination possible and returning the best .