devbelly

문제 https://www.acmicpc.net/problem/1893 알고리즘 KMP 풀이 문제 이해가 조금 어려운(?) 문제였습니다. $S$ 에서 $W$ 를 찾되, $W$를 $A$에 따라 시프트 하며 새로운 $W'$에 대해서도 KMP를 수행하는 문제입니다. KMP를 수행하는 방식은 어렵지 않으니 남은 과제는 $W$를 어떻게 움직여야 하나 고민해야 합니다. 시프트를 수행할 때, 우리가 알아야할 정보는 현재 문자의 다음 문자를 알면 되므로 $conv$ 배열을 통하여 해결하도록 합시다. KMP를 $A$ 만큼 수행하고 새로운 $W'$를 만드는 데는 $W$ 길이 만큼이 소요되므로 시간 복잡도는 $O(A(W+S))$입니다. 코드 #include #define rep(i,n) for(int i=0;i tc; wh..

문제 https://www.acmicpc.net/problem/1701 알고리즘 KMP 풀이 실패 함수의 의미를 알고 있어야 풀 수 있는 문제였습니다. $fail[x]$ = $y$ 는 문자열$S$의 처음 $x$+1 글자에서 일치하는 접두사/접미사 중 최대길이는 $y$ 실패 함수를 기록할 때, 위 정의에 따라 두 번 이상 등장하는 부분 문자열(접두사, 접미사)이라는 조건 만족하게 됩니다. 그리고 원래 문자열의 모든 접두사만 고려하는 실패 함수는 중간에서 등장하는 부분 문자열을 고려하지 못하므로 KMP를 반복하며 원래 문자열의 맨 앞을 하나씩 제거하는 방식을 사용합니다. 원래의 실패함수내에서 $j$의 의미는 현재까지 매칭한 개수를 의미합니다. 그러나 원래 문자열의 맨 앞을 제거하기 위해 사용한 $k$로 인하..

문제 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..