devbelly

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