열심히해보겠씁니다

KMP 알고리즘의 응용 문제. 문제를 잘 읽고 다시 생각해보면 전체가 될 수 있는 부분 문자열 중 최소 길이를 구하라는 뜻과 같다. 즉 s = abcabcabcabc 문자열이 있다면 답의 후보는 abc, abcabc 가 되고, 그 중 더 짧은 abc 를 구하라는 얘기이다. KMP 알고리즘은 찾고 싶은 문자열의 접두사/접미사 중 최대 길이의 Index를 미리 구해놓는데, 그 연장선이다. 인덱스를 부여하는 것과 이 문제를 연관시켜보자. 1. 부분 문자열은 항상 index 0 부터 시작해야 한다. -> abcabcabcabc 라면 부분 문자열은 bca 형태로 만들어질 수 없고 항상 a 부터 시작해야 한다. 2. 부분 문자열의 중간을 건너뛸 수 없다. -> abcabcabcabc 에서 ab(c)abc 형태로 만..

KMP 알고리즘의 입문 문제이다. 문제에 친절하게 KMP 알고리즘에 대한 설명이 있으니 천천히 읽어보면 좋을 것 같다. KMP 알고리즘은 크게 두 가지 단계를 거친다. 1. 찾으려는 문자열(P)의 겹치는 접두사와 접미사를 찾아 그 위치를 기록하기. 2. 본 문자열(T)에서 찾으려는 문자열 찾기. 위 두 단계는 유사한 과정을 거치며, 접두사와 접미사가 중복되는 것을 이용하여 불필요한 탐색 횟수를 건너뛰려는 것이 궁극적인 목표이다. KMP 알고리즘을 이용하면 for 문 한 번에 모두 검색이 가능하므로 찾으려는 문자열의 길이를 M으로 두면, 1번 단계에서 O(M) 본 문자열의 길이를 N 으로 두면, 2번 단계에서 O(N)의 시간복잡도가 요구된다. 1,2 의 공통적인 핵심 아이디어는, 중복을 건너뛴다는 것이다...