searchsolve.java

从给定的字母矩阵中查找给定的字典所包含的字符串

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

/**
 * This is the critical class of this program. <p>
 * It reads every words from the dictionary file and search the word 
 * in the matrix. 
 * Finally, it writes the found words to the output file. 
 * 
 * @author Ting Chen  0122070
 * @version 1.0    2003/5/30
 * @see java.util.StringTokenizer
 */
public class SearchSolve 
{
	/** The name of the output file */
	String outPutFile;

	/** The dictionary file */
	BufferedReader dic;	

	/** The data structure to store and sort the found words */
	BST BSTtree;
	
	/**
	 * This is the constructor for class SearchSolve.
     * It initializes the BSTtree for storing and sort the words 
	 */
	public SearchSolve()
	{	
    BSTtree = new BST();	
	}

  /**
	 * At first, it reads in the letter matrix, stores the letters
	 * in a n * n two-dimension char array. Then it traverses the char array
	 * and records the information of each pair of adjacent letters in a 26 * 26
	 * list array. That is reading a letter and looking at its up,down,left,right
	 * letters, and saving the information in the list.  <p>
	 * Then after initialization, it reads one word from the dictionary, split the String
	 * into characters, then look for the pair of the first two letters in the list array.
	 * After retrieved the information of the first two letters of the letter matrix, it push the 
	 * position of the first two letters to a stack, and mark the valid n*n array in order to avoid
	 * duplicately allocating the letters in the letter matrix.  <p>
	 * After that, it peeks the top element of the stack, search for the four positions of the second 
	 * letter, if at least one of them contains the third letter of the word, push the position into
	 * the stack, otherwise pop the second letter and the first letter from the stack, try another pair
	 * of the first letter and the second letter if has one or search the next word. <p>
	 * While the stack is not empty, repeat the peek, search, push(while has one)/pop(while find none).  <p>
	 * The word which are found are stored in a BST tree, when all the search finishes, traverse the BST tree
	 * in in-order and write the result to the out*.txt.  <p>
	 * Above is the simple description of the algorithm of this program.  <p>
	 * Look at the design document for more detail information. 
	 *
	 * @param br BufferedReader of the dictionary file.
	 * @exception  Throws input/output exception.
	 */
	public void readText(BufferedReader br) throws IOException
	{
		String readInLine;  //储存读入的单词
		int lineNumber;  //字母矩阵的大小
		StringTokenizer tokens;  //分析读入矩阵
		char[][] chars;  //储存读入的字母矩阵
		
		dic = new BufferedReader( new FileReader("dict"));    

    readInLine = br.readLine();
		tokens = new StringTokenizer(readInLine);
		lineNumber = tokens.countTokens();   //字符矩阵的大小	

		chars = new char[lineNumber][lineNumber];	

    //读入矩阵
		for ( int i = 0; i < lineNumber; i++ )
		{
			for ( int j = 0; j < lineNumber ; j++ )
			{
				chars[i][j] = (tokens.nextToken()).charAt(0);
			}
      readInLine = br.readLine();
			if ( readInLine != null )
				tokens = new StringTokenizer(readInLine);				
		}
    
		//将每一对相邻结点的信息保留在26*26的list矩阵中
    AList[][] letterTree;	
		letterTree = new AList[26][26];

		for ( int i = 0;  i < 26; i++ )
		{
			for ( int j = 0; j < 26; j++ )
			{
				letterTree[i][j] = new AList();
			}			
		}

		int[] elem = new int[4];
		int helpK;
		int helpM,helpN;

   //遍历整个字母矩阵，把每一对相邻结点的信息储存在这个list array中
		for ( int i = 0; i < lineNumber; i++ )
		{
			for ( int j = 0; j < lineNumber ; j++ )
			{				
			  helpM = i - 1;
				helpN = j;
				helpK = (int)chars[i][j] - 97;
			
			  //搜索当前字母上面的字母。
				if ( helpM >= 0 )
				{
					elem = new int[4];

					elem[0] = i;
					elem[1] = j;
					elem[2] = i-1;
					elem[3] = j;

					letterTree[helpK][(int)chars[helpM][j] - 97].append(elem);				
				}
        
				helpM = i + 1;			
				
				//搜索当前字母下面的字母。
				if ( helpM < lineNumber )
				{
					elem = new int[4];
					elem[0] = i;
					elem[1] = j;
					elem[2] = helpM;
					elem[3] = j;			

					letterTree[helpK][(int)chars[helpM][j] - 97].append(elem);				
				}			

				helpM = i;
				helpN = j - 1;			
        
				//搜索当前字母左面的字母。
				if ( helpN >= 0 )
				{
					elem = new int[4];

					elem[0] = i;
					elem[1] = j;
					elem[2] = i;
					elem[3] = helpN;		

					letterTree[helpK][(int)chars[i][helpN] - 97].append(elem);				
				}
			 
				helpN = j + 1;				

        //搜索当前字母右面的字母。
				if (helpN < lineNumber)
				{
					elem = new int[4];
					elem[0] = i;
					elem[1] = j;
					elem[2] = i;
					elem[3] = helpN;		

					letterTree[helpK][(int)chars[i][helpN] - 97].append(elem);					
				}			
			}			
		}				

		String readWord;
		int[] indexStr = new int[3];
		int[] helpStr = new int[3];	
		int[] indexStrHelp = new int[3];
		int m,n,k;
		LinkStack resultStack = new LinkStack();
		boolean[][] valid;		
		boolean hasOne;
	
		readWord = dic.readLine();

    valid = new boolean[lineNumber][lineNumber];				
   		
	  //读入单词分析查找
		while( readWord!= null )
	  {		
			loop:
			{		
			//从相关list中找到单词开头两个字母的位置信息，开始分析，
			 for ( int i = letterTree[(int)(readWord.charAt(0)) - 97][(int)(readWord.charAt(1)) - 97].length() - 1; i >= 0; i-- )
			 {
				int[] help = (int[])(letterTree[(int)(readWord.charAt(0)) - 97][(int)(readWord.charAt(1)) - 97].get(i));
				
				indexStr[0] = help[0];   //字母x坐标
				indexStr[1] = help[1];   //字母y坐标
				indexStr[2] = 0;   //字母在单词中的位置

				valid[indexStr[0]][indexStr[1]] = true;   //标记为已经使用过。
				
				resultStack.push(indexStr);		 //压入第一个字母
				
				indexStr = new int[3];

				indexStr[0] = help[2];
				indexStr[1] = help[3];
				indexStr[2] = 1;			

				resultStack.push(indexStr);		//压入第二个字母
				
				
				while( !resultStack.empty() )
				{
					indexStrHelp = resultStack.peek();			

					m = indexStrHelp[0];
					n = indexStrHelp[1];
					k = indexStrHelp[2];				

	 				if ( k == readWord.length() - 1 )
					{
						//已找到 ，退出for这个循环
						BSTtree.insert(readWord);
						break loop;						 
					}
					else
				  {		
						 hasOne = false;

             //查找当前字母上面的字母是否为单词中的下一个字母，是则压入栈中。
						 if ( ( (m-1) >= 0 ) &&(!valid[m-1][n]) 
							 && (chars[m-1][n] == readWord.charAt(k+1)))
					   {
							  helpStr = new int[3];
				  	    helpStr[0] = m-1;
						    helpStr[1] = n;
						    helpStr[2] = k+1;

								hasOne = true;
								
								resultStack.push(helpStr);							
						 }
							   	
						 //查找当前字母下面的字母是否为单词中的下一个字母，是则压入栈中。
					  if ( ( (m+1) < lineNumber ) && (!valid[m+1][n]) 
							&& (chars[m+1][n] == readWord.charAt(k+1)))
				  	{
					  	helpStr = new int[3];
					  	helpStr[0] = m+1;
						  helpStr[1] = n;
						  helpStr[2] = k+1;    
							
							hasOne = true;
							
							resultStack.push(helpStr);
							
						}
											
						 //查找当前字母左面的字母是否为单词中的下一个字母，是则压入栈中。
						if ( ( (n-1) >= 0 ) && (!valid[m][n-1]) 
				  		&& (chars[m][n-1] == readWord.charAt(k+1)))
					  {					
							helpStr = new int[3];
							helpStr[0] = m;						
							helpStr[1] = n-1;					
							helpStr[2] = k+1;
							
							hasOne = true;
							
							resultStack.push(helpStr);						
					  }
				
				    //查找当前字母右面的字母是否为单词中的下一个字母，是则压入栈中。
					  if ( ( (n+1) < lineNumber ) && (!valid[m][n+1]) 
							 && (chars[m][n+1] == readWord.charAt(k+1)))
				    {
						  helpStr = new int[3];
							helpStr[0] = m;
							helpStr[1] = n+1;
							helpStr[2] = k+1;				
							
							hasOne = true;					

							resultStack.push(helpStr);				
						}
				
						if ( hasOne )
						{
							//如果对于单词中的下一个字母至少找到一个，标记当前位置为已使用过的。
							 valid[m][n] = true;					
						}
						else
						{
							//没有在上下左右找到下一个字母，弹出当前字母。
							valid[m][n] = false;
					   	resultStack.pop();					
						
						  int[] helpStr0 = new int[3];
							int cou = k - 1;
             
						  //假如前面已经没有可以搜索的字母，均从栈中弹出。
						  while(!resultStack.empty())
							{
								helpStr0 =  resultStack.peek();

								if ( helpStr0[2] <= cou)
								{
								 
									valid[m][n] = false;
									int[] helpStr1 = (int[])(resultStack.pop());
									valid[helpStr1[0]][helpStr1[1]] = false;						
									cou--;
								}
								else
									break;
								
								helpStr0 = new int[3];
							}				
						}					
					}
				}//end while loop				
			  resultStack = new LinkStack();			
			}  
			
			} //end loop		
		  
			resultStack = new LinkStack();

      //根据字母矩阵大小选择不同的重置valid的方式，小的矩阵遍历修改，大的则再请求一个新的对象。
	  	if ( lineNumber < 100 )
	  	{
				for (int i =0; i < lineNumber ; i++ )
			  {
					for (int j =0; j < lineNumber ; j++ )
					{
						if (valid[i][j])
						{	
							valid[i][j] = false;
						}
					}
			  }
	  	}
			else
			{
				valid = new boolean[lineNumber][lineNumber];		
			}
			
		  readWord = dic.readLine();
		}		

		//输出结果到文件中
		BSTtree.in( outPutFile );	
	}
}