devbelly

문제 https://www.acmicpc.net/problem/1786 알고리즘 KMP 풀이 기초 KMP 적용문제입니다. 인덱스가 1부터 시작하는 점에 유의하며 풀면 됩니다. 주어지는 두 문자열의 길이가 각각 $N$,$M$ 일 때, 시간복잡도는$O(N+M)$ 입니다. ++ 개인적으로 실패함수 작성시 $1-BASED$ 방식이 코드작성 측면에서 더 깔끔한 것 같습니다. 이후 KMP 문제에서 실패함수를 응용하는 문제들을 만나게 되면 이유를 느끼실수 있습니다. 저는 $0-BASED$ 를 기준으로 코드를 작성하였으니, KMP 알고리즘을 입문하시는 분은 $1-BASED$ 방식으로 입문하시는 것을 추천드립니다. 코드 #include #define rep(i,n) for(int i=0;i 0 && T[i] != P[j..