이름 정하기
시간 제한2초메모리 제한512 MB
문자열 S와 정수 K가 주어질 때, S를 부분 문자열로 K번 이상 포함하는 가장 짧은 문자열의 길이를 구한다.
문제
욱제는 새로 산 컴퓨터에 이름을 붙이려고 한다.
새로 산 컴퓨터의 이름은 욱제가 가장 좋아하는 문자열인 가 최소 번 부분 문자열로 등장해야 한다. 가능한 이름이 여러 가지면 길이가 가장 짧아야 한다.
와 가 주어졌을 때, 욱제가 새로 산 컴퓨터 이름의 길이를 구해보자.
입력
첫째 줄에 와 가 주어진다. 는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. 는 1,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 욱제가 새로 산 컴퓨터 이름의 길이를 출력한다.