KMP 알고리즘...

#include<iostream>
#include<string>
#include<process.h>
#include<stdlib.h>
using namespace std;

class KMP
{
 private :
  char array[200], pat[10]; // array는 비교할 문자열, pat는 찾을 문자열
  int temp; // 비교할 문자의 실패함수의 현재 값
  int f_pat[10];
  int i, k; // 함수 제어의 필요한 함수
  int n, l; // n은 찾을 문자열의 길이 l은 비교할 문자열의 길이
 public :
  KMP()
  {
   temp=-1, i=0, k=0;
   for(i=0; i<200; i++)
   {
    array[i]=NULL;
   }
  }
  int path(int k, int i); // 문자열 비교 함수
  void input(); // 문자열들을 입력 받음
  void makefaile(); // 실패함수를 만드는 함수
  void test(int k, int i); // 같은 문자열을 찾아내는 함수
};

void main()
{
 KMP *valu;
 valu = new KMP;
 valu -> input();
}

void KMP::makefaile()
{
 int val=0, p=0; // val은 실패함수에 들어갈 값이고 p는 함수 제어 변수이다.
 int j=1, i; // k는 실패함수 배열 이동값이고 i는 함수 제어 변수이다.

 f_pat[j-1]=-1; // 실패 함수의 첫값은 어떻게 해도 -1이 이다.
 if(pat[j]==pat[j-1])
 {
  f_pat[j]=0;
 }
 else
 {
  f_pat[j]=-1;
 }
 j++;
 while(n+1 > j)
 {
  if(f_pat[j-1] == -1)
  {
   if(pat[0]==pat[k])
   {
    f_pat[j]=0;
   }
   else
   {
    f_pat[j]=-1;
    val=0;
   }
  }
  else if(f_pat[j-1] != -1)
  {
   for(i=1; i<j-1; i++)
   {
    if(pat[i]==pat[j] && pat[i-1]==pat[j-1]) // 전에 같은 패턴이 있었다면
    {
     f_pat[j] = ++val;
     p++;
     break;
    }
   }
   if(p==0)
   {
    f_pat[j]=-1;
   }
  }
  j++; // 실패함수 배열 위치 다음 칸으로 이동
  p=0; // 제어변수 p 0으로 초기화
 }
}

int KMP::path(int k, int i)
{
 temp++;
 if(temp==n) // 동일 문자열을 찾았다면
 {
  cout << i-n << "byte ~ " << i << "byte" << endl; // 찾은 문자열 출력
  if(i>l-n-1) // 더 이상 비교할 필요가 없어지면 종료
  {
   _exit(0); // 프로그램 종료
  }
  k=0; // 찾을 문자열 위치를 처음으로 이동
  i--; // 비교할 문자열을 처음부터 다시 비교하기 위해 이동
  temp=-1; // 비교할 문자열 실패함수 값 초기화
  if(array[i]==pat[k])
  {
   i++; k++;
   path(k, i);
  }
  else if(array[i]!=pat[k])
  {
   i++;
   test(k, i);
  }
 }
 if(array[i]==pat[k]) // 다음 같이 일치 한다면
 {
  i++; k++;
  path(k, i); // 이동한 다음 같을 확인 하는 재귀함수
 }
 else if(array[i]!=pat[k]) // 일치하지 않는다면
 {
  k=f_pat[temp]; // f_pat 값을 pat의 ID값으로 변경
  temp=k; // 이동 후의 ID값으로 변경
  k++; // 변경 후 그 다음 값과 비교하기 위해
  if(array[i]==pat[k]) // 변경후 동일한 확인
  {
   k++; i++;
   path(k, i);
  }
  else if(array[i]!=pat[k]) // 새로운 패턴인 경우
  {
   temp=-1; // 더 이상 값은 값이 없기 때문에 -1로 초기화
   i++;
   test(k, i);
  }
 }
 return 1;
}

void KMP::input()
{
 cout << "Input String( ~ 200btye) : ";
 cin >> array;
 cout << "Input String( ~ 10byte) : ";
 cin >> pat;
 n=strlen(pat)-1;
 l=strlen(array);
 makefaile();
 i=0; // i값 비교를 위해 초기화
 test(k, i);
}

void KMP::test(int k, int i)
{
 while(i < l)
 {
  if(i==l-1) // 끝가지 갔다면 종료
  {
   _exit(0); // 프로그램 종료
  }
  if(array[i]==pat[k])
  {
   i++; k++;
   path(k, i);
  }
  else if(array[i]!=pat[k])
  {
   i++; // 비교할 문자열만 한칸 이동
  }
 }
}

DS 실습시간에 뜬금없이 나온 큐즈... 라기보다는 일일 과제... "오늘 12시까지 제출하세요~"라고 웃으며 말하던 조교의 얼굴이 아직도 기억난다. 솔직히 완벽한 KMP알고리즘이라고는 말할 수 없다... 사실 실패 함수가 제대로 작동하는지 의문 -_-;; 하지만!! 결과 값은 제대로 나온다는 거~ 위에 주석을 좀더 친절하게 달아 주고 싶지만... 이제와서는 달라고 해도 못단다... 내가 짠거지만 뭔소리인지 -_-;;; 새삼 주석의 힘을 실감한다...