템플릿

바이트아사르(Byteasar)는 집 벽에 꽤 긴 문양을 새기려고 한다. 이를 위해 먼저 글자들이 잘려 있는 적절한 템플릿(형판)을 만든다. 벽의 원하는 위치에 이 템플릿을 대고 그 위를 덧칠하면, 템플릿에 있는 모든 글자를 한 번에 "찍어"낼 수 있다(일부 글자만 골라 찍는 것은 불가능하다). 같은 칸을 여러 번 덧칠해도 되므로, 템플릿을 서로 다른 위치에 겹쳐 가며 여러 번 찍는 것도 허용된다. 템플릿의 글자들은 서로 붙어 있다(중간에 빈칸이 없다).

문양 전체를 그대로 담은 템플릿을 만들 수도 있지만, 바이트아사르는 비용을 줄이기 위해 가능한 한 짧은 템플릿을 만들고 싶어 한다.

다음을 수행하는 프로그램을 작성하라.

• 바이트아사르가 벽에 새기려는 문양(문자열)을 표준 입력에서 읽는다.
• 그 문양을 만들어 내는 데 필요한 템플릿의 최소 길이를 구한다.
• 결과를 표준 출력에 쓴다.

정리하면, 문자열 $S$가 주어질 때, $T$의 복사본들을 $S$ 위의 여러 위치에 찍어 $S$를 정확히 만들 수 있는 문자열 $T$ 가운데 가장 짧은 것의 길이 $|T|$를 구하는 문제이다. 이때 다음을 만족해야 한다.

• 각 찍기는 $S$ 안에 완전히 들어와야 하며(밖으로 넘어갈 수 없다), 찍은 자리에서 $T$의 글자들이 $S$의 해당 글자들과 모두 일치해야 한다(따라서 각 찍기 위치는 $S$ 안에서 $T$가 나타나는 위치이다).
• 찍기들은 서로 겹쳐도 되지만, 이들이 합쳐져 $S$의 모든 위치를 빠짐없이 덮어야 한다.

표준 입력의 첫째 줄(유일한 줄)에 한 개의 단어가 주어진다. 이는 바이트아사르가 벽에 새기려는 문양이다. 이 단어는 영어 소문자로만 이루어지며, 길이는 1 이상 500,000 이하이다.

표준 출력의 첫째 줄(유일한 줄)에 정수 하나를 출력한다. 이는 필요한 템플릿의 최소 글자 수(최소 길이)이다.