devbelly

문제 https://www.acmicpc.net/problem/10747 알고리즘 KMP 풀이 KMP를 통해서 제거할 문자열의 위치를 찾아내는 접근까지는 쉽습니다. 검열할 문자를 없앤 후, 우리는 이전의 상태로 돌아가야 하는데, 이를 위해 $matchCnt$배열을 사용합니다. $matchCnt [i]$ = 문자열 S의 $i$까지 봤을 때, 문자열 T와 일치하는 길이 벡터에 지금까지 확인한 S글자들을 담으며, 제거할 문자열을 찾았다면 벡터에서 T의 길이만큼 제거합니다. 그 후 이전의 상태, 즉 제거한 문자열의 첫 문자가 들어오기 직전의 상태로 돌아가야 합니다. KMP에서 $j$의 의미는 지금까지 매칭된 길이와도 동일하므로(구현에 따라 차이가 날 수 있음, 이 코드에선 매칭된 길이 -1입니다) $j$값을 $..

문제 https://www.acmicpc.net/problem/13276 알고리즘 KMP 해설 다양한 풀이가 있는 문제입니다. 라빈 카프를 이용한 해싱, 가장 효율적인 Suffix Array 등 이 있지만 구현이 가장 쉬운 KMP로 풀었습니다. $S$에 대해 두 문자열$A$,$B$가 나타나는 위치를 KMP를 통해 찾은 후, 부분 문자열이 될 수 있는 것들을 담았습니다. $vector$에 직접 부분 문자열을 담게 되면 메모리 초과가 발생하니, $set$을 통해 부분 문자열을 담고, 자연스레 중복도 제거하도록 합시다. 시간 복잡도는 모든 인덱스에서 부분 문자열이 시작하고 끝날 수 있으므로 $O(N^2)$ + 해시 접근입니다. #include #include #define rep(i,n) for(int i=0..

문제 https://www.acmicpc.net/problem/1787 알고리즘 KMP, 동적 계획법 풀이 추정할 수 있는 문자열의 길이가 가장 길기 위해선 일치하는 prefix와 suffix가 가장 짧아야 함을 알 수 있습니다. 우리가 실패함수를 만들게 되면 일치하는 prefix와 suffix가 가장 긴 길이가 담겨 있게 됩니다. 문제에서 요구하는 것과는 정반대입니다. prefix와 suffix가 일치하는 길이가 1 이상인 가장 짧은 길이를 얻는 것은 동적 계획법을 통해 해결 가능합니다. $cache[i]$ = 문자열의 길이가 $i+1$ 일 때, 동일한 prefix와 suffix의 길이중 0을 제외한 가장 짧은 값 현재 문자열의 길이를 $k$라 할 때, 일치하는 가장 긴 길이는 $fail[k-1]$ 이..

문제 https://www.acmicpc.net/problem/16229 알고리즘 KMP, Z 풀이 실패 함수의 다양한 특징들을 사용해서 푸는 문제입니다. 이 이상 어떻게 응용되는지는 모르겠으나, 제가 느끼기론 모든 성질을 다 사용한 것 같습니다. 이 문제에서 실패 함수를 $1-BASED$로 구현하게 되면 깔끔해지는 이유를 알 수 있습니다. 실패 함수의 특징에 대한 설명은 아래 사진으로 대체하겠습니다. (설명을 자세하게 해주신 doju님 감사합니다) 이제 위 사진의 모든 정보를 이용해 접근을 해봅시다. 우리는 1번 특징을 사용해 실패 함수를 계속 반복하게 되면 주어진 문자열 $S$ 에 대해 suffix와 prefix가 동일한 모든 길이$a$를 얻게 됩니다. $a$를 안다면 당연히 2번 특징을 사용해 모든..

문제 https://www.acmicpc.net/problem/2401 알고리즘 KMP, 동적 계획법 풀이 직관적인, 나이브한 방법으로 생각을 해봅시다. 짧은 문자열들을 긴 문자열의 각 위치마다 일일이 매칭을 시도해보는 방법을 떠올릴 수 있습니다. 긴 문자열 $L$에서 짧은 문자열$I$이 시작할 수 있는 위치를 찾는데 한 개가 아닌 $N$개의 문자열에 대해서 해야 합니다. 우리는 이 방법을 최적화할 수 있는 방법을 알고 있습니다. 긴 문자열에서 짧은 문자열을 찾는 알고리즘. 즉 KMP입니다. 매칭은 빠르게 했으니 일일이 시도하는 문제는 동적 계획법을 통하여 풀 수 있습니다. 시간 복잡도는 $O(N(L+I)+NL)$입니다. 매칭한 결과를 저장할 수 있는 효율적인 방법을 생각해보도록 합시다. 처음에 저는 벡..

문제 https://www.acmicpc.net/problem/4354 알고리즘 KMP 풀이 드디어 만나게 된 $S$에서 $W$를 찾는 단순한 KMP가 아닌, 실패 함수 자체만을 사용하는 문제입니다. 실패 함수에는 여러 성질 및 특징이 있지만, 자주 만나게 되는 세 가지 큰 특징이 있습니다. 그 중 하나를 소개하겠습니다. 문자열에서 A글자의 패턴을 만들 수 있음과 문자열의 앞쪽(N-A)글자와 뒤쪽 (N-A)글자가 같음은 동치 이 문제를 풀땐 위 특징을 적극 활용하여 풀어봅시다. 주어진 문자열 $S$에 대하여 실패함수를 구했다면, 우리는 $fail[slen-1]$ 이 가장 긴 접두사, 접미사의 길이임을 알게 됩니다. 문제에서 원하는 가장 큰 $n$을 구하기 위해선 반복되는 문자열의 길이가 가장 짧아야 하므..

문제 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$로 인하..