#include <stdio.h>
#include <string.h>

// 문자열 string 안에서 패턴 pat이 처음 나타나는 위치를 찾는 패턴 매칭 프로그램

/**
--------------------------
|        |       |       |   pat (찾으려고하는 패턴)
--------------------------
    ^ j             ^ lsatp
*/

// 검색 대상 문자열 string

// index   0 1 2 3 4 5 6 7 8 9
//         ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
// string  a b a b b a a b a a
//                   └─┬─┘
//                       a a b  

// main()
//  │
//  ├─ s = "ababbaabaa"
//  ├─ p = "aab"
//  │
//  ├─ ss → s
//  ├─ pp → p
//  │
//  └─ nfind(ss, pp)
//          │
//          ├─ string → "ababbaabaa"
//          ├─ pat    → "aab"
//          │
//          └─ 패턴 검색
//               ↓
//            결과 반환 (패턴발견: 발견한 시작위치반환/패턴없음: -1반환)
//               ↓
//           main의 result
//               ↓
//           printf()

// start
//  ↓
//  0 1 2
//  └─┬─┘
//    패턴을 놓아보는 범위
//      ↑
//  endmatch

// index
//  0   1   2   3   4   5   6   7   8   9   10
// ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬────┐
// │ a │ b │ a │ b │ b │ a │ a │ b │ a │ a │ \0 │
// └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴────┘
//  ↑
//  s

// index
//  0   1   2   3
// ┌───┬───┬───┬────┐
// │ a │ a │ b │ \0 │
// └───┴───┴───┴────┘
//  ↑
//  p

// string = a b a b b a a b a a
//          ↑                 ↑
//       start              lasts

// pattern = a a b
//           ↑   ↑
//           0  lastp

int nfind(char *string, char *pat){ //string: 검색할 문자열의 시작 위치, pat:찾으려는 문자열의 시작 위치

    int i, j, start = 0;
    int lasts = strlen(string)-1; //string의 마지막 문자의 인덱스
    int lastp = strlen(pat)-1; //pat의 마지막 인덱스
    int endmatch = lastp; //검색대상범위값의 오른쪽의 끝

    for(i=0; endmatch<= lasts; endmatch++, start++)
    {
       if(string[endmatch]==pat[lastp]){ //패턴 전체를 처음부터 비교하기 전에 마지막 문자부터 먼저 비교, string과 pat 끝의 인덱스의 값이 일치하지않으면 굳이 앞의값을 검사할 필요가 없기 때문
           for(i=start, j=0; j<lastp && string[i]==pat[j]; i++,j++);
       
        if(j==lastp) //패턴의 시작값 == 마지막값 => 검색이 끝
            return  start; //성공
       }
    }
    return -1;
}

int main() {

    char s[] = {"ababbaabaa"};
    char p[] = {"aab"};
    char *ss = s;
    char *pp = p;
    
    int result;

    result = nfind(ss, pp);
    
    printf("result: %d\n", result);
    
    return 0;
}