Estou tentando implementar um programa que receba uma entrada do usuário, divida essa sequência em tokens e pesquise no dicionário as palavras dessa sequência. Meu objetivo para a string analisada é fazer com que cada token seja uma palavra em inglê

Por exemplo

Input:
       aman

Split Method:
      a man
      a m an
      a m a n
      am an
      am a n
      ama n

Desired Output:
      a man

Atualmente, tenho esse código que faz tudo até a parte de saída desejada:

    import java.util.Scanner;
import java.io.*;

public class Words {

    public static String[] dic = new String[80368];

    public static void split(String head, String in) {

        // head + " " + in is a segmentation 
        String segment = head + " " + in;

        // count number of dictionary words
        int count = 0;
        Scanner phraseScan = new Scanner(segment);
        while (phraseScan.hasNext()) {
            String word = phraseScan.next();
            for (int i=0; i<dic.length; i++) {
                if (word.equalsIgnoreCase(dic[i])) count++;
            }
        }

        System.out.println(segment + "\t" + count + " English words");

        // recursive calls
        for (int i=1; i<in.length(); i++) {
            split(head+" "+in.substring(0,i), in.substring(i,in.length()));
        }   
    }

    public static void main (String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        System.out.print("Enter a string: ");
        String input = scan.next();
        System.out.println();

        Scanner filescan = new Scanner(new File("src:\\dictionary.txt"));
        int wc = 0;
        while (filescan.hasNext()) {
            dic[wc] = filescan.nextLine();
            wc++;
        }

        System.out.println(wc + " words stored");

        split("", input);

    }
}

Sei que existem maneiras melhores de armazenar o dicionário (como uma árvore de pesquisa binária ou uma tabela de hash), mas não sei como implementá-la

Estou empolgado em como implementar um método que verifique a cadeia de caracteres da divisão para ver se cada segmento era uma palavra no dicionári

Qualquer ajuda seria ótimo, obrigad