devbelly

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

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