// Arup Guha
// 7/22/2014
// Implementations of three string matching algorithms:
//     1. Brute Force
//     2. Boyer-Moore
//     3. Knuth-Morris-Pratt

import java.util.*;
import java.io.*;

public class StrMatch {

    final public static boolean DEBUG = false;
    final public static boolean PRINTTIME = true;
    final public static int MAX = 10000000;
    final public static long MOD = 1000000007L;

    public static char[] text;
    public static char[] pattern;
    public static int tLen;
    public static int pLen;

    public static void main(String[] args) throws Exception {

        /***
        Hard-coded tests.
        String t = "hipishipphiphoorayhowhohowdydoodyhippohippopotamusthisisahiphiphippopoppoippohippo";
        String p = "hippo";
        String t = "abbbababababababbbababababababab";
        String p = "abab";

        text = t.toCharArray();
        pattern = p.toCharArray();
        tLen = text.length;
        pLen = pattern.length;
        ***/

        // Read in the text and pattern.
        Scanner stdin = new Scanner(System.in);
        System.out.println("Enter the text file.");
        String fileName = stdin.next();
        loadText(fileName);
        System.out.println("Please enter the pattern, all lower case.");
        String p = stdin.next();
        pattern = p.toCharArray();
        pLen = pattern.length;

        long t1 = System.currentTimeMillis();
        ArrayList<Integer> bf = bruteForce();
        long t2 = System.currentTimeMillis();
        ArrayList<Integer> bm = boyerMoore();
        long t3 = System.currentTimeMillis();
        ArrayList<Integer> kmp = knuthMorrisPratt();
        long t4 = System.currentTimeMillis();
        ArrayList<Integer> rk = rabinKarp();
        long t5 = System.currentTimeMillis();

        // See if other algorithms caused a problem.
        if (!equal(bf, bm)) System.out.println("Boyer Moore Problem.");
        else if (!equal(bf, kmp)) System.out.println("Knuth-Morris-Pratt Problem.");
        else if (!equal(bf, rk)) System.out.println("Rabin-Karp Problem.");


        if (PRINTTIME) {
            System.out.println("bf = "+(t2-t1)+" ms.");
            System.out.println("bm = "+(t3-t2)+" ms.");
            System.out.println("kmp = "+(t4-t3)+" ms.");
            System.out.println("rk = "+(t5-t4)+" ms.");
        }

        // Print Matching Locations.
        if (DEBUG) {
            for (Integer x: bf)
                System.out.print(x+" ");
            System.out.println(bf.size());
        }
    }

    public static void loadText(String fileName) throws Exception {

        BufferedReader fin = new BufferedReader(new FileReader(fileName));

        // Read into tmp buffer
        char[] tmp = new char[MAX];
        int size = fin.read(tmp, 0, MAX);

        // Now copy over alphabetic characters into tmp2.
        char[] tmp2 = new char[size];
        tLen = 0;
        for (int i=0; i<size; i++)
            if (Character.isAlphabetic(tmp[i]))
                tmp2[tLen++] = Character.toLowerCase(tmp[i]);

        // Now, we can size this.
        text = new char[tLen];
        for (int i=0; i<tLen; i++) text[i] = tmp2[i];
        fin.close();
    }

    // Returns true iff a and b are identical lists in the same order.
    public static boolean equal(ArrayList<Integer> a, ArrayList<Integer> b) {
        if (a.size() != b.size()) return false;
        for (int i=0; i<a.size(); i++)
            if (a.get(i).compareTo( b.get(i)) != 0)
                return false;
        return true;
    }

    // Returns a list of starting indexes within the text of all matches with
    // the pattern, using brute force.
    public static ArrayList<Integer> bruteForce() {

        ArrayList<Integer> matches = new ArrayList<Integer>();

        // Go through each valid starting character.
        for (int i=0; i<=tLen-pLen; i++) {

            // Match as many letters from the beginning.
            int j = 0;
            while (j < pLen && pattern[j] == text[i+j]) j++;

            // Got it!
            if (j == pLen) matches.add(i);
        }

        return matches;
    }

    // Returns a list of starting indexes within the text of all matches with
    // the pattern, using the Boyer-Moore Algorithm.
    public static ArrayList<Integer> boyerMoore() {

        ArrayList<Integer> matches = new ArrayList<Integer>();

        // For each letter, store the last index that contains it.
        int[] last = new int[26];
        Arrays.fill(last, -1);
        for (int i=0; i<pLen; i++)
            last[pattern[i] - 'a'] = i;

        // cur is index matching from the back.
        int cur = pLen-1;
        while (cur < tLen) {

            // Match from the back.
            int j = cur, k = pLen-1;
            while (k >= 0 && pattern[k] == text[j]) {
                j--;
                k--;
            }

            // Made it, it's a match.
            if (k < 0) matches.add(j+1);

            // Advance the spot in the back that we're matching.
            cur = Math.max(cur+1, cur+pLen-last[text[cur]-'a']-1);
        }

        return matches;
    }

    // Returns the fail array as defined in the KMP algorithm.
    public static int[] getFail() {

        int[] fail = new int[pLen];
        int k = 0;

        // Iterate through pattern.
        for (int i=1; i<pLen; i++) {

            // Looking for matches from the previous spot in the pattern.
            while (k > 0 && pattern[k] != pattern[i])
                k = fail[k-1];

            // Case when these two letters match, so we can add one to the match length.
            if (pattern[k] == pattern[i]) k++;

            // Store result.
            fail[i] = k;
        }

        // Return failure array.
        return fail;
    }

    // Returns a list of starting indexes within the text of all matches with
    // the pattern, using the Knuth-Morris-Pratt Algorithm.
    public static ArrayList<Integer> knuthMorrisPratt() {

        ArrayList<Integer> matches = new ArrayList<Integer>();

        // Need this to run KMP.
        int[] fail = getFail();

        // Iterate through text.
        int i = 0, j = 0;
        while (i < tLen) {

            // Processing a matching character.
            if (pattern[j] == text[i]) {

                // Got a match, reset i and j accordingly.
                if (j == pLen-1) {
                    matches.add(i-pLen+1);
                    j = fail[j-1];
                }

                // Since we matched, both just move up.
                else {
                    i++;
                    j++;
                }
            }

            // Update j to next possible location.
            else if (j > 0)
                j = fail[j-1];

            // Just move up one in the text.
            else
                i++;
        }

        return matches;
    }

    public static ArrayList<Integer> rabinKarp() {

        ArrayList<Integer> matches = new ArrayList<Integer>();

        // Calculate hash value of target string.
        long target = getPatternHash();

        // Calculate current hash AND 26^pLen%MOD.
        long curHash = 0, place = 1;
        for (int i=0; i<pLen; i++) {
            curHash = (26*curHash + text[i] - 'a')%MOD;
            place = (26*place)%MOD;
        }

        // See if first substring worked.
        if (curHash == target && bfVerify(0)) matches.add(0);

        // Roll through each other substring of length pLen.
        for (int i=pLen; i<tLen; i++) {

            // Calculate next hash by adding next character, and removing contribution
            // of the character pLen previous to this one.
            curHash = (26*curHash + text[i] - 'a' - place*(text[i-pLen]-'a'))%MOD;
            if (curHash < 0) curHash += MOD;

            // See if this is a fit.
            if (curHash == target && bfVerify(i-pLen+1)) matches.add(i-pLen+1);
        }

        // Ta da!!!
        return matches;
    }

    // Returns the hash value of the pattern.
    public static long getPatternHash() {
        long ans = 0;
        for (int i=0; i<pLen; i++)
            ans = (26*ans + pattern[i] - 'a')%MOD;
        return ans;
    }

    // Returns true iff pattern matches text[loc...loc+pLen-1].
    public static boolean bfVerify(int loc) {
        for (int i=0; i<pLen; i++)
            if (pattern[i] != text[i+loc])
                return false;
        return true;
    }
}