Exercise 09

Part A

Implement a class TextSearchKMPCached that extends TextSearchKMP. You need to override the method findFirst(String text, String target) to be more efficient. Instead of recomputing the needed data structures for each target input, those should be internally "cached", e.g., in a map. This means that each single token would be computed only once. If findFirst is called a second time with the same target input (but possibly different text), then the computation would be speeded up by re-using the data structures from the cache.

Implement a test class TextSearchKMPCachedTest that extends TextSearchTestTemplate. If your implementation of TextSearchKMPCached is "functionally" correct, then all tests should pass.

Part B

Write a class PatternExamplesImp that implements the interface org.pg4200.ex09.PatternExamples.

Implement a test class PatternExamplesImpTest that extends org.pg4200.ex09.PatternExamplesTestTemplate. If your implementation of PatternExamplesImp is correct, then all tests should pass.

Part C

Study the source code of TextSearchKMP. Once you think you fully understand it, write its implementation on paper (e.g., using a pen), without looking at the source code. Once done, compare what you wrote with the actual implementation.

Solutions

Solutions to this exercise can be found in the solutions module, under the org.pg4200.sol09 package.