매 위치마다 패턴길이 만큼 비교하니까 시간 복잡도는 O(MN)인데
패턴 매칭에 사용되는 알고리즘: 라빈-카프 알고리즘 / 보이어-무어 알고리즘 / KMP 알고리즘
고지식한 알고리즘(Brute Force) : 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일히 비교하는 방식으로 동작
KMP(Knuth-Morris-Pratt Algorithm)
패턴 안에 반복적인 형태를 보이면 유리
패턴과 비교하다가 패턴 불일치가 발생하면 실패함수(배열: 패턴 불일치 발생하면 패턴 포인터인 j가 어느위치로 돌아갈지 지시해주는 역할)를 봐라! 실패함수가 가라는 위치로 가라!
시간 복잡도 : O(M + N)