PreAnalysis.java

/**
 * PreAnalysis interface for students to implement their algorithm selection logic
 * 
 * Students should analyze the characteristics of the text and pattern to determine
 * which algorithm would be most efficient for the given input.
 * 
 * The system will automatically use this analysis if the chooseAlgorithm method
 * returns a non-null value.
 */
public abstract class PreAnalysis {
    
    /**
     * Analyze the text and pattern to choose the best algorithm
     * 
     * @param text The text to search in
     * @param pattern The pattern to search for
     * @return The name of the algorithm to use (e.g., "Naive", "KMP", "RabinKarp", "BoyerMoore", "GoCrazy")
     *         Return null if you want to skip pre-analysis and run all algorithms
     * 
     * Tips for students:
     * - Consider the length of the text and pattern
     * - Consider the characteristics of the pattern (repeating characters, etc.)
     * - Consider the alphabet size
     * - Think about which algorithm performs best in different scenarios
     */
    public abstract String chooseAlgorithm(String text, String pattern);
    
    /**
     * Get a description of your analysis strategy
     * This will be displayed in the output
     */
    public abstract String getStrategyDescription();
}


/**
 * Default implementation that students should modify
 * This is where students write their pre-analysis logic
 */
class StudentPreAnalysis extends PreAnalysis {
    
    @Override
    public String chooseAlgorithm(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        // Case 1: If the pattern is longer than the text or empty
        if (m > n || m == 0) {
            return "Naive";
        }

        // Case 2: If the pattern is very short (1-2 letters)
        if (m <= 2) {
            return "Naive";
        }

        // Case 3: Alphabet analysis (Is it a small character set like DNA or Binary?)
        boolean isSmallAlphabet = true;
        int checkLimit = Math.min(n, 20);
        for (int i = 0; i < checkLimit; i++) {
            char c = text.charAt(i);
            if ("ACGT01 \t\n".indexOf(c) == -1) {
                isSmallAlphabet = false;
                break;
            }
        }

        // 4. Strategic Decision Making
        if (isSmallAlphabet) {
            // KMP is very good for structures with repetitions and small alphabets like DNA.
            return "KMP";
        } else if (m > 10) {
            // If the pattern is long and the alphabet is large (like normal English text)
            // GoCrazy (Sunday Algorithm) makes great jumps.
            return "GoCrazy";
        } else {
            // Boyer-Moore is reliable for other standard cases.
            return "BoyerMoore";
        }
    }

    
    @Override
    public String getStrategyDescription() {
        return "My Strategy: Using Naive for short patterns, KMP for small alphabets (DNA), GoCrazy (Sunday) for long patterns, and BoyerMoore for other cases.";
    }
}


/**
 * Example implementation showing how pre-analysis could work
 * This is for demonstration purposes
 */
class ExamplePreAnalysis extends PreAnalysis {

    @Override
    public String chooseAlgorithm(String text, String pattern) {
        int textLen = text.length();
        int patternLen = pattern.length();

        // Simple heuristic example
        if (patternLen <= 3) {
            return "Naive"; // For very short patterns, naive is often fastest
        } else if (hasRepeatingPrefix(pattern)) {
            return "KMP"; // KMP is good for patterns with repeating prefixes
        } else if (patternLen > 10 && textLen > 1000) {
            return "RabinKarp"; // RabinKarp can be good for long patterns in long texts
        } else {
            return "Naive"; // Default to naive for other cases
        }
    }

    private boolean hasRepeatingPrefix(String pattern) {
        if (pattern.length() < 2) return false;

        // Check if first character repeats
        char first = pattern.charAt(0);
        int count = 0;
        for (int i = 0; i < Math.min(pattern.length(), 5); i++) {
            if (pattern.charAt(i) == first) count++;
        }
        return count >= 3;
    }

    @Override
    public String getStrategyDescription() {
        return "Example strategy: Choose based on pattern length and characteristics";
    }
}

/**
 * Instructor's pre-analysis implementation (for testing purposes only)
 * Students should NOT modify this class
 */
class InstructorPreAnalysis extends PreAnalysis {

    @Override
    public String chooseAlgorithm(String text, String pattern) {
        // This is a placeholder for instructor testing
        // Students should focus on implementing StudentPreAnalysis
        return null;
    }

    @Override
    public String getStrategyDescription() {
        return "Instructor's testing implementation";
    }
}