possible sentences

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        s = s.substring(4,s.length()-1);
        String ss = in.nextLine();
        ss = ss.substring(6);
        String[] dict = ss.split(",");
        for (int i=0;i<dict.length;i++){
            dict[i] = dict[i].substring(1,dict[i].length()-1);
        }
        ArrayList<String>[] lists = new ArrayList[s.length()];
        for (int i=0;i<dict.length;i++){
            int key = bf(s,dict[i]);
            if (key == -1)
                continue;
            if (lists[key] == null){
                ArrayList<String> list = new ArrayList<>();
                list.add(dict[i]);
                lists[key] = list;
            }else
                lists[key].add(dict[i]);
        }
        dfs(lists,"",0,s.length());
        st.sort(new Comparator<String>() {
            public int compare(String o1, String o2) {
                return o2.compareTo(o1);
            }
        });
        System.out.println(st.toString());
    }
    private static ArrayList<String> st = new ArrayList<>();
    private static void dfs(ArrayList<String>[] lists,String s,int index,int length){
        if (index == length){
            String str = s.substring(0,s.length()-1);
            st.add(str);
            return;
        }
        if (lists[index] == null)
            return;
        for (int i=0;i<lists[index].size();i++){
            String str = s;
            String ls = lists[index].get(i);
            str = str+ls+" ";
            dfs(lists,str,index+ls.length(),length);
        }
    }

    private static int bf(String s,String t){
        int i=0,j=0;
        int index = 0;
        while (i<s.length() && j<t.length()){
            if (s.charAt(i) == t.charAt(j)){
                i++;j++;
            }else{
                index++;
                i = index;
                j = 0;
            }
        }
        if (j == t.length()){
            return index;
        }
        return -1;
    }
}