Word Finder

The Task

You are to design an algorithm to search for words in an array of letters. For example, given a word list and the array

0 1 2 3 4 5 6 7 8 9 10 11
text g t c a n d l e t j a q

one would expect the output

2 can
2 candle
3 a
3 an
3 and
6 let
10 a

where the number is an offset from the start of the array being searched, and the string is a word from the dictionary that was found at that offset. Note that several words can start at the same offset, and the same word can be found in multiple places. Note also that words can overlap.

The inputs to your algorithm are

an array of strings, containing a dictionary of search keys. You may assume that this is arranged in ascending order, and that there are no duplicates. However it is possible for one key to be a prex of another, as with "can" and "candle" in the above example. In such cases the shorter word comes before the longer one. an array of characters (a string) to be searched.

Both of these inputs can be quite large.

The output of your algorithm will be a list of locations of matches, each consisting of an offset from the beginning of the text and the string found. This list can be in whatever order you choose.

You should work out a solution in pseudocode, and then translate it into Java, with the arrays of characters represented by Java strings.

There are several ways to solve this problem. A solution that produces correct results can achieve a good pass, but to achieve the higher marks your solution will need to be efcient for large dictionaries. (The fact that the dictionary will be ordered could be useful here.)

Java class

I have supplied a small project WordFinder.zip containing a Java class Location and an interface WordFinder that I want you to use. You are to add to that project a class MyWordFinder of the following form:

package wordfinder;
import java.util.ArrayList;

public class MyWordFinder implements WordFinder {

public ArrayList findWords(String[] dictionary, String text) {
// ... your code here ...
}
}

Your class may contain additional elds and methods, as long as they are private.

At the top of the le, you should include a comment of no more than 200 words. This should include:

the strategy of your algorithm a justied worst-case time complexity for the algorithm, expressed in big-O notation Each loop in your code should be annotated with a comment giving the invariant of the loop.