[Java] Hash Table과 AVL Tree를 이용한 Pattern Matching 2/2

자료구조 / 2002년 2학기 / 문병로 교수님

[Matching.java 2/2]

public class Matching
{
       private static String inputFileName = "testpaper.txt";                                        // 인풋 파일 이름
       public static int k = 6;                                                                                                // 검색의 최소 한계가 되는 글자수
       private static LinkedList[] foundLists;                                                                        // 글자를 검색한 결과가 저장될 곳
       private static HashTable ht;                                                                                        // 해쉬 테이블

       public static void main(String[] args) throws IOException
       {
               BufferedReader in = new BufferedReader(new FileReader(inputFileName));
               int numOfLine = 0;
               try
               {
                       numOfLine = Integer.parseInt(in.readLine());                                        // 첫줄은 라인 갯수
               }
               catch (NumberFormatException e)
               {
                       System.out.println("The number of Line is illegal!");                        // 인티저로 파싱이 안될 경우
                       System.exit(0);
               }

               ht = new HashTable();                                                                                                // 해쉬테이블 생성
               String buffer = in.readLine();
               for (int count = 1; buffer != null; count++)                                                // 첫번째 라인부터 한줄씩 읽어서 테이블에 넣음
               {
                       ht.insert(count, buffer);
                       buffer = in.readLine();
                       numOfLine--;
               }
               if (numOfLine != 0)                                                                                                        // 처음 읽은 라인 수가 맞지 않으면
               {
                       System.out.println("Line Counting Error!");
                       System.exit(0);
               }

               buffer = "";                                                                                                                // 버퍼를 초기화
               System.out.print("> Search substring? ");
               int nextChar = System.in.read();                                                                        // 입력을 한글자씩 읽으면서

       while (nextChar != -1)                                                                                                // EOF가 나올때까지
       {
           if (nextChar == '\n')                                                                                        // 입력이 끝나면
                       {
                               find(buffer);                                                                                                // 그 스트링이 있는지 찾고
                               buffer = "";                                                                                                // 다시 버퍼를 초기화하고
                               System.out.print("> Search substring? ");                                        // 다시 입력받음
                       }
           else if (nextChar != '\r')                                                                                // 읽은것을 버퍼에 모음. '/r'인 경우는 제외
                               buffer += (char)nextChar;
                       nextChar = System.in.read();
       }
       }

       public static void find(String s)
       {
               if (s.length() < k)                                                // 길이가 짧으면 검색 실패
               {
                       System.out.println("Please insert more than or equal to " + k + " characters.");
                       return;
               }
               
               int numOfSub = s.length() - k + 1;                                                        // 가능한 substring의 갯수
               foundLists = new LinkedList[numOfSub];
               for (int i=0; i<numOfSub; i++)
               {
                       foundLists[i] = ht.findSub(s.substring(i, i + k));                // 서브스트링이 있는지 찾음
                       if (foundLists[i] == null)
                       {
                               System.out.println("No Such String!");                                // 만약 한 substring이라도 발견이 안되면 전체 string이 없는것!
                               return;
                       }
               }
               
               foundLists[0].resetIteration();                                                                // 맨처음 리스트. 즉, 첫 6글자의 substring이 발견된 리스트
               int x, y;
               boolean temp = true;
               while (foundLists[0].moreToIterate())
               {
                       x = foundLists[0].getCurrentData1();
                       y = foundLists[0].getCurrentData2();
                       if (isExist(x, y))                                                                                // 만약 발견이 되었으면 그 pair를 출력하라.
                       {
                               if (temp)
                               {
                                       System.out.print("Found : ");                                        // 출력을 깔끔하게 하기 위함.
                                       temp = false;
                               }
                               else
                                       System.out.print(", ");
                               System.out.print("(" + x + ", " + y + ")");
                       }
                       foundLists[0].goToNext();                                                                // 리스트의 다음 노드(다음으로 찾은곳)
               }
               System.out.println();
       }

       private static boolean isExist(int x, int y)
       {
               return isExist(0, x, y);
       }

       private static boolean isExist(int listNum, int x, int y)        // 첫번째 리스트에 (x,y)가 있으면 두번째 리스트에는 (x,y+1)이 있어야 하므로..
       {
               if (listNum == foundLists.length)                        // 만약 마지막 list까지 왔다면, 이 string은 찾는 스트링이 맞음!
                       return true;
               else if (foundLists[listNum].isExist(x,y))        // 그게 아닌데, 현재 검색중인 리스트에 (x,y) 쌍이 있다면
                       return isExist(listNum + 1, x, y+1);        // 다음 리스트에 (x,y+1)쌍이 있는지 검사하라
               else
                       return false;                                                        // 검색이 되지 않았으면 false를 리턴
       }
}