import java.io.*;


// Puzzle class interface: solve word search puzzle
//
// CONSTRUCTION: with no initialzier
// ******************PUBLIC OPERATIONS******************
// int solvePuzzle( )   --> Print all words found in the
//                          puzzle; return number of matches


public class WordSrch
{
    private static final int MAX_ROWS    =     64;
    private static final int MAX_COLUMNS =     64;
    private static final int MAX_WORDS   = 100000;


    /**
     * Constructor for WordSrch class.
     * Prompts for and reads puzzle and dictionary files.
     */
    public WordSrch( )
    {
        puzzleStream = openFile( "Enter puzzle file" );
        wordStream   = openFile( "Enter dictionary name" );
        System.out.println( "Reading files..." );
        readPuzzle( );
        readWords( );
    }

    /**
     * Routine to solve the word search puzzle.
     * Performs checks in all eight directions.
     * @return number of matches
     */
    public int solvePuzzle( )
    {
        int matches = 0;

        for( int r = 0; r < rows; r++ )
            for( int c = 0; c < columns; c++ )
                for( int rd = -1; rd <= 1; rd++ )
                    for( int cd = -1; cd <= 1; cd++ )
                        if( rd != 0 || cd != 0 )
                            matches += solveDirection( r, c, rd, cd );

        return matches;
    }


    /**
     * Search the grid from a starting point and direction.
     * @return number of matches
     */
    private int solveDirection( int baseRow, int baseCol, int rowDelta, int colDelta )
    {
        String charSequence = "";
        int numMatches = 0;
        int searchResult;

        charSequence += theBoard[ baseRow ][ baseCol ];

        for( int i = baseRow + rowDelta, j = baseCol + colDelta;
                 i >= 0 && j >= 0 && i < rows && j < columns;
                 i += rowDelta, j += colDelta )
        {
            charSequence += theBoard[ i ][ j ];
            searchResult = prefixSearch( theWords, charSequence, numEntries );

            if( !theWords[ searchResult ].startsWith( charSequence ) )
                break;

            if( theWords[ searchResult ].equals( charSequence ) )
            {
                numMatches++;
                System.out.println( "Found " + charSequence + " at " +
                                    baseRow + " " + baseCol + " to " +
                                    i + " " + j );
            }
        }
        return numMatches;
    }



    /**
     * Performs the binary search for word search
     * using one comparison per level.
     * Assumes a and n are OK.
     * @param a the sorted array of strings.
     * @param x the string to search for.
     * @param n the number of strings in the array.
     * @return last position examined;
     *     this position either matches x, or x is
     *     a prefix of the mismatch, or there is no
     *     word for which x is a prefix.
     */
    private static int prefixSearch( String [ ] a, String x, int n )
    {
        int low = 0;
        int high = n - 1;

        while( low < high )
        {
            int mid = ( low + high ) / 2;
            if( a[ mid ].compareTo( x ) < 0 )
                low = mid + 1;
            else
                high = mid;
        }

        return low;
    }

    /**
     * Print a prompt and open a file.
     * Retry until open is successful.
     * Program exits if end of file is hit.
     */
    private BufferedReader openFile( String message )
    {
        String fileName = "";
        FileReader theFile;
        BufferedReader fileIn = null;

        do
        {
            System.out.println( message + ": " );

            try
            {
                fileName = in.readLine( );
                if( fileName == null )
                     System.exit( 0 );
                theFile = new FileReader( fileName );
                fileIn  = new BufferedReader( theFile );
            }
            catch( IOException e )
              { System.err.println( "Cannot open " + fileName ); }
        } while( fileIn == null );

        System.out.println( "Opened " + fileName );
        return fileIn;
    }
        
    /**
     * Routine to read the grid.
     * Checks to ensure that the grid is rectangular.
     * Checks to make sure that capacity is not exceeded is omitted.
     */
    private void readPuzzle( )
    {
        String oneLine;

        try
        {
            if( ( oneLine = puzzleStream.readLine( ) ) == null )
            {
                rows = 0;
                return;
            }
            columns = oneLine.length( );
            for( int i = 0; i < columns; i++ )
                theBoard[ 0 ][ i ] = oneLine.charAt( i );

            for( rows = 1;
                    ( oneLine = puzzleStream.readLine( ) ) != null;
                          rows++ )
            {
                if( oneLine.length( ) != columns )
                    System.err.println( "Puzzle is not rectangular" );

                for( int i = 0; i < columns; i++ )
                    theBoard[ rows ][ i ] = oneLine.charAt( i );
            }
        }
        catch( IOException e ) { }
    }


    /**
     * Routine to read the dictionary.
     * Error message is printed if dictionary is not sorted.
     * Check is made to avoid exceeding maxWords.
     */
    private void readWords( )
    {
        numEntries = 0;

        try
        {
            while( ( theWords[ numEntries ] = wordStream.readLine( ) ) != null )
            {
                if( numEntries != 0 &&
                  theWords[ numEntries ].compareTo( theWords[ numEntries - 1 ] ) < 0 )
                {
                    System.err.println( "Dictionary is not sorted... skipping" );
                    continue;
                }
                else if( ++numEntries >= MAX_WORDS )
                    break;
            }

            if( wordStream.ready( ) )
                System.err.println( "Warning: unread data - increase MAX_WORDS" );
        }
        catch( IOException e ) { }
    }

      // Cheap main
    public static void main( String [ ] args )
    {
        WordSrch p = new WordSrch( );
        System.out.println( "Solving..." );
        p.solvePuzzle( );
    }


    private int rows;
    private int columns;
    private int numEntries;
    private char theBoard[ ][ ] = new char[ MAX_ROWS ][ MAX_COLUMNS ];
    private String [ ] theWords = new String[ MAX_WORDS ];
    private BufferedReader puzzleStream;
    private BufferedReader wordStream;
    private BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );
}