devbelly

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