import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * 單詞搜索迷宮
 * 
 * */
public class WordSearch
{
 /**
 * 在構(gòu)造函數(shù)中構(gòu)造兩個(gè)輸入流，單詞的輸入流，和表格的輸入流
 * */
  public WordSearch( ) throws IOException
  {
    puzzleStream = openFile( "輸入表格文件路徑：" );
    wordStream  = openFile( "輸入單詞文件路徑：" );
    System.out.println( "文件讀取中..." );
    readPuzzle( );
    readWords( );
  }
  /**
   * @return matches 共有多少個(gè)單詞匹配
   * 按照每個(gè)位置從八個(gè)方向搜索
   * rd 表示行上得增量，eg:rd=-1，表示向上一行
   * cd 表示列上得增量  eg:cd=-1。表示向左一步
   * 所以rd=1,cd=0表示南
   * rd=-1,cd=0表示北，
   * rd=-1,cd=1,表示東北
   */
  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;
  }
  /**
   * 在指定的坐標(biāo)上，按照給定的方向搜索，返回匹配的單詞數(shù)量
   * @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 );
      /**
       * 下面的 if( searchResult == theWords.length )
       * 必須要判斷，否則會(huì)出現(xiàn)越界的危險(xiǎn)，及當(dāng)最后一個(gè)單詞之匹配前綴時(shí)，返回的是索引-1
       * */
      if( searchResult == theWords.length )
        break;
      /**
       * 如果沒有響應(yīng)的前綴，直接跳過這個(gè)基點(diǎn)的搜索，即使繼續(xù)搜索，做的也是無用功
       * */
      if( !theWords[ searchResult ].startsWith( charSequence ) )
        break;
      if( theWords[ searchResult ].equals( charSequence ) )
      {
        numMatches++;
        System.out.println( "發(fā)現(xiàn)了 " + charSequence + " 在 " +
                  baseRow+1 + "行  " + baseCol + " 列   " +
                  i + " " + j );
      }
    }
    return numMatches;
  }
  /**
   * 先解釋Arrays.binarySearch(Object[] ,Object)
   * 使用二進(jìn)制搜索算法來搜索指定數(shù)組，以獲得指定對(duì)象。在進(jìn)行此調(diào)用之前，
   * 必須根據(jù)數(shù)組元素的自然順序 對(duì)數(shù)組進(jìn)行升序排序（通過上面的 Sort(Object[] 方法）。
   * 如果沒有對(duì)數(shù)組進(jìn)行排序，則結(jié)果是不明確的。（如果數(shù)組包含不可相互比較的元素（例如，字符串和整數(shù)），
   * 則無法 根據(jù)數(shù)組元素的自然順序?qū)?shù)組進(jìn)行排序，因此結(jié)果是不明確的。）
   * 如果數(shù)組包含多個(gè)等于指定對(duì)象的元素，則無法保證找到的是哪一個(gè)。 
   */
  private static int prefixSearch( String [ ] a, String x )
  {
    int idx = Arrays.binarySearch( a, x );
    if( idx < 0 )
      return -idx - 1;
    else
      return idx;
  }
  /**
   * 讀取文件內(nèi)容，獲得輸入流
   */
  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;
  }
  /**
   * 讀入表格
   * */
  private void readPuzzle( ) throws IOException
  {
    String oneLine;
    List<String> puzzleLines = new ArrayList<String>( );
    if( ( oneLine = puzzleStream.readLine( ) ) == null )
      throw new IOException( "No lines in puzzle file" );
    columns = oneLine.length( );
    puzzleLines.add( oneLine );
    while( ( oneLine = puzzleStream.readLine( ) ) != null )
    {
      if( oneLine.length( ) != columns )
        System.err.println( "Puzzle is not rectangular; skipping row" );
      else
       puzzleLines.add( oneLine );
    }
    rows = puzzleLines.size( );
    theBoard = new char[ rows ][ columns ];
    int r = 0;
    for( String theLine : puzzleLines )
      theBoard[ r++ ] = theLine.toCharArray( );
  }
  /**
   * 讀取已經(jīng)按照字典排序的單詞列表
   */
  private void readWords( ) throws IOException
  {
    List<String> words = new ArrayList<String>( );
    String lastWord = null;
    String thisWord;
    while( ( thisWord = wordStream.readLine( ) ) != null )
    {
      if( lastWord != null && thisWord.compareTo( lastWord ) < 0 )
      {
        System.err.println( "沒有按照字典順序排序，此次跳過" );
        continue;
      }
      words.add( thisWord.trim() );
      lastWord = thisWord;
    }
    theWords = new String[ words.size( ) ];
 theWords = words.toArray( theWords );
  }
   // Cheap main
  public static void main( String [ ] args )
  {
    WordSearch p = null;
    try
    {
      p = new WordSearch( );
    }
    catch( IOException e )
    {
      System.out.println( "IO Error: " );
      e.printStackTrace( );
      return;
    }
    System.out.println( "正在搜索..." );
    p.solvePuzzle( );
  }
  private int rows;
  private int columns;
  private char [ ][ ] theBoard;
  private String [ ] theWords;
  private BufferedReader puzzleStream;
  private BufferedReader wordStream;
  private BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );
}