Assignment 2 #

This assignment is about implementing a simple string search algorithm.

Description #

We all familiar with KMP string search algorithm. In this assignment, please implement a variant of KMP string search algorithm, which allows the pattern string to contain wildcards. A wildcard character (?) can match any character. For example, the pattern string a?c can match abc, acc, adc, etc. Please use the following abstract class definition:

public abstract class AbstractStringSearch {
    /**
     * Preprocess the pattern string.
     * @param pattern The pattern string.
     */
    void preprocessPattern(String pattern) {}

    /**
     * Search for the first occurrence of the pattern string in the text string.
     * @param text The text string to be searched.
     * @return The index of the first occurrence of the pattern string in the text string, or -1 if the pattern string is not found.
     */
    int search(String text) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    int search(String pattern, String text) {
        preprocessPattern(pattern);
        return search(text);
    }
}

The example package can be downloaded here.

There are no competitions in this assignment. You shall implement your tests and ensure your implementation can pass all your tests.

Your implementation shall also pass hidden tests. The hidden tests will be used to evaluate your implementation along with your own tests. There are 2 points for passing the hidden tests.

Requirements #

• You need to write at least 3 different test cases. Do not test with large amount of data, or with multi-threading.
• You should implement and modify KMP algorithm to support wildcards.

Submission #

It is extremely important that you are following the naming conventions for your class, tests, files, and submissions. If the automatic system fails to recognise your submissions or failed to execute them, your assignment will be treated as NOT SUBMITTED. Late submissions are NOT allowed and will NOT be accepted.

Requirements #

• Your submission must be a zip file and the file name must be your student number. Example: 202312345.zip
• Your submitted zip file must contain StringSearch.java and StringSearchTest<student number>.java. The structure shall like:

202312345.zip
	|- StringSearch.java
	|- StringSearchTest000000000.java

• The StringSearch.java file must include a public class, StringSearch, which extends the AbstractStringSearch class.
• You can change anything in your submission.
• No third-party libraries or dependencies.
• Your code must be working with JDK 17 and up.
• All your own tests shall pass.
• Code style is important. You need to follow Java naming conventions and ensure there are no unnecessary extra new lines, spaces (e.g., additional spaces at the end of lines, a line with only spaces), etc.
• Do not declare packages. You must use the default package.

Validate your submission #

You can validate your submission here.

Passing the validation DOES NOT means your submission is correct. It only means your submission is in the correct format and can be executed by the automatic system. You still need to ensure your submission is correct.