Given a string s and an array of smaller strings T, design a method to search s for each small string in T.

First, create a suffix tree for s. For example, if your word were bibs, you would create the following tree:
                                                             I               S
                                            B
                                     I                               B
                                                    S
                             B                                              S
                     S
Then, all you need to do is search for each string in T in the suffix tree. Note that if “B” were aword, you would come up with two locations.

1        public class SuffixTree {
2                SuffixTreeNode root = new SuffixTreeNode();
3                public SuffixTree(String s) {
4                         for (int i = 0; i < s.length(); i++) {
5                               String suffix = s.substring(i);
6                               root.insertString(suffix, i);
7                         }
8                }
9           
10               public ArrayList<Integer> getIndexes(String s) {
11                        return root.getIndexes(s);
12               }
13       }
14   
15       public class SuffixTreeNode {
16               HashMap<Character, SuffixTreeNode> children = new
17                                                                 HashMap<Character, SuffixTreeNode>();
18               char value;
19               ArrayList<Integer> indexes = new ArrayList<Integer>();
20            public SuffixTreeNode() { }
21        
22            public void insertString(String s, int index) {
23                   indexes.add(index);
24                   if (s != null && s.length() > 0) {
25                           value = s.charAt(0);
26                           SuffixTreeNode child = null;
27                           if (children.containsKey(value)) {
28                                   child = children.get(value);
29                           } else {
30                                   child = new SuffixTreeNode();
31                                   children.put(value, child);
32                           }
33                           String remainder = s.substring(1);
34                           child.insertString(remainder, index);
35                   }
36            }
37        
38            public ArrayList<Integer> getIndexes(String s) {
39                   if (s == null || s.length() == 0) {
40                           return indexes;
41                   } else {
42                           char first = s.charAt(0);
43                           if (children.containsKey(first)) {
44                                   String remainder = s.substring(1);
45                                   return children.get(first).getIndexes(remainder);
46                           }
47                   }
48                   return null;
49            }
50     }
51   
52     public class Question {
53            public static void main(String[] args) {
54                   String testString = “mississippi”;
55             String[] stringList = {“is”, “sip”, “hi”, “sis”};
56             SuffixTree tree = new SuffixTree(testString);
57                   for (String s : stringList) {
58                  ArrayList<Integer> list = tree.getIndexes(s);
59                  if (list != null) {
60                             System.out.println(s + “: “ + list.toString());
61                  }
62                   }
63            }
64     }