KMP 알고리즘

패턴 매칭 알고리즘 중

1. 부르트 포스 방법.
   첫글자 부터 맞는지 확인 하는 방법

int pattern_find(char *string, char *pat)
{ /* match from the beginning of pattern */
    int k, j, start = 0;
    int lasts = strlen(string)-1;
    int lastp = strlen(pat)-1;

    for (k = 0; k <= lasts - lastp; k++) {
        for (j = 0; j <= lastp; j++)
            if (string[k+j] != pat[j]) break; // k+j == i의 의미로 해석하자
        if ( j == lastp+1) return k; /* pattern start index in string */
    }
    return -1; /* not found */
}

2. N-find

int nfind(char *string, char *pat)
{ /* match the last character of pattern first, and then match from the beginning */
    int i, j, start = 0;
    int lasts = strlen(string)-1;
    int lastp = strlen(pat)-1;
    int endmatch = lastp;

    for (i = 0; endmatch <= lasts; endmatch++, start++) {
        if (string[endmatch] == pat[lastp]) {
            for (j = 0, i = start; j < lastp && string[i] == pat[j]; i++,j++);
            if ( j == lastp) return start; /* successful */
        }
    }
    return -1;
}

3. KMP

int pmatch(char *string, char *pattern)
{ /* Knuth, Morris, Pratt string matching algorithm */
    int s = 0, p = 0;
    int length_str= strlen(string);
    int length_pat = strlen(pattern);

    while ( s < length_str && p < length_pat ) {
        if (string[s] == pattern[p]) { s++; p++; }
            else {
                    if (p == 0) s++;
                    else p = failure[p-1]+1;
            }
     }
        return ( (p == length_pat) ? (s-length_pat), -1);
}

위 코드를 쓰기 위해서는 Failure 함수를 써야함 -> 패턴을 찾아야 함

void fail(char *pat)
{
  int s, m, length = strlen(pat);
  failure[0] = -1;
      for (s=1; s < length; s++) {
  // decide failure[s]; (어디까지 최대로 같은가)
          m = failure[s-1]; // 바로 앞은 m 까지 같았다.
          while ((m>=0) && (pat[m+1] != pat[s]))
              m = failure[m];
          if (pat[m+1] == pat[s]) failure[s] = m+1;
          else failure[s] = -1;
      }    
}