/**
 * Boyer_Moore.java
 *
 *
 * Created: Fri May 10 17:31:39 2002
 *
 * @author Lars Ehrhardt
 * @version
 */

import java.io.*;

public class Boyer_Moore {

    /* provided by Prof. Becker */
    private static int[] compute_D( String spat )
    {
        int    m       = spat.length();
        char[] pat     = new char[m+1];
        int[]  rborder = new int[m+1];
        int[]  D       = new int[m+1];
        int    i, j, t, l, s, j1;

        /* convert String to char array */

        for ( i=0 ; i<m ; i++ )
            pat[i+1] = spat.charAt( i );

        /* initialization */

        rborder[m] = 0;
        D[m] = 1;
        for (j1 = m - 1; j1 >= 0; j1--)
            {
                rborder[j1] = 1;
                D[j1] = m;
            }

        /* phase 1 */

        i = m - 1;
        j = 1;
        while ( i > 0 ) {
            while (((i - j + 1) >= 1) && (pat[m - j + 1] == pat[i - j + 1])) {
                j++;
                rborder[i - j + 1] = j;
            }
            if ( j > 1 ) {
                s = m - i;
                t = i - j + 1;
                if ((t + s) > s)
                    D[t + s] = Math.min(s, D[t+s]);
            }
            i = i - j + rborder[m - j + 1];
            j = Math.max(rborder[m - j + 1], 1);
        }

        /* phase 2 */

        t = rborder[0];
        l = 1;
        while ( t > 0 ) {
            s = m - t + 1;
            for(j = l; j <= s ; j++)
                D[j] = Math.min( D[j], s );
            t = rborder[s];
            l = s + 1;
        }
        return D;
    }

    /**
     * Describe <code>openFile</code> method here.
     *
     * @param file a <code>String</code> value
     * @return a <code>StringBuffer</code> value
     */
    private static StringBuffer openFile(String file) {
        DataInputStream inputfile = null;

        try {
            inputfile = new DataInputStream(new FileInputStream(file));
        } catch (FileNotFoundException e) {
            System.out.println("Error: Could not open " + file + " !");
            System.exit(10);
        } // end of try-catch

        StringBuffer input = new StringBuffer();
        try {
            while ( inputfile.available() > 0) {
                input.append( (char) inputfile.read());
            } // End while.
        } catch (IOException e) {

        } // end of try-catch

        try {
            inputfile.close();
        } catch (IOException e) {
            System.out.println("Could not close file " + file + " !");

        } // end of try-catch

        return input;
    }

    /**
     * Describe <code>doBoyerMoore</code> method here.
     *
     * @param algorithm a <code>String</code> value
     * @param pat a <code>String</code> value
     * @param file a <code>String</code> value
     */
    private static void doBoyerMoore(String algorithm, String pat, String file) {

        StringBuffer text   = openFile(file);
        int selalgorithm    = Integer.parseInt(algorithm);
        int i               = 1;
        int n               = text.length();
        int m               = pat.length();
        int[] D             = compute_D(pat);
        int compares_succ   = 0;
        int compares_unsucc = 0;

        while (i <= n - m + 1) {
            int j = m;
            while (j >= 1 && pat.charAt(j-1) == text.charAt(i+j-1-1)) {
                j = j - 1;
            }
            if (j == 0)
                compares_succ++;
            else
                compares_unsucc++;

            int last = 0;
            if (selalgorithm == 1 || selalgorithm == 2) {
                if (i+j-1<n) {
                    char c = text.charAt(i+j-1);
                    last = pat.lastIndexOf(c);
                    if (last < 0) last = 0;
                }
            } // end of if (selalgorithm == 1 || selalgorithm == 2)

            switch (selalgorithm) {
            case 0:
                i = i + D[j]; //Boyer & Moore (with a shift table)
                break;
            case 1:
                i = i + Math.max(D[j],j-last); //Boyer + Moore with added occurence-shifts
                break;
            case 2:
                i = i + Math.max(1,j-last); //Boyer + Moore with only occurence-shifts
                break;
            default:
                i = i + 1; //naiv algorithm
                break;
            }
        }

        /*
          Output our analysis
        */

        System.out.println("--- analaysis ---");
        System.out.print("Algorithm               : ");

        switch (selalgorithm) {
        case 0:
            System.out.println("Boyer & Moore with a shift table");
            break;
        case 1:
            System.out.println("Boyer & Moore with a shift table and occurence shifts");
            break;
        case 2:
            System.out.println("Boyer & Moore with occurence shifts");
            break;
         default:
            System.out.println("naiv string algorithm");
            break;
        }

        System.out.println("Length of text          : " + n);
        System.out.println("Pattern                 : \"" + pat + "\" (length: " + m + ")");
        System.out.println("Unsuccesfull comparisons: " + compares_unsucc);
        System.out.println("Successfull comparisons : " + compares_succ);
    }

    public static void main (String[] args) {

        if (args.length != 3) {
            System.out.println("Error: invalid parameters!");
            System.out.println("Usage: java Boyer_Moore <algorithm> <pattern> <file>");
            System.out.println("<algorithm> 0: boyer & moore with shift table");
            System.out.println("<algorithm> 1: boyer & moore with shift table and occurence shifts");
            System.out.println("<algorithm> 2: boyer & moore with occurence shifts");
            System.exit(10);
        }

        doBoyerMoore(args[0],args[1],args[2]);

    } // end of main ()

}// Boyer_Moore