cho.sh

연속 반복 문자열

문자열 S 뒤에 소문자 k개를 자유롭게 붙였을 때, 어떤 문자열이 두 번 이상 연속해 나타나는 가장 긴 부분 문자열의 길이를 구한다.

어려움9문자열문자열 매칭동적 계획법아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

연속 반복 문자열이란, 같은 문자열이 연속해서 등장하는 것을 의미한다. "abcabc"는 "abc"가 연속해서 등장했기 때문에, "dd"는 "d"가 연속해서 등장, "qwertyqwerty"는 "qwerty"가 연속해서 등장했기 때문에, 모두 연속 반복 문자열이다.

문자열 S가 주어졌을 때, 뒤에 k개의 글자를 더 추가해서 만들 수 있는 문자열의 부분 문자열 중에서 연속 반복 문자열이면서 길이가 가장 긴 것을 구해보자.

입력

첫째 줄에 문자열 S, 둘째 줄에 k(1 ≤ k ≤ 200)가 주어진다. 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 200보다 작거나 같다.

출력

첫째 줄에 S의 뒤에 k개의 글자를 더 추가해서 만들 수 있는 문자열의 부분 문자열 중에서 연속 반복 문자열이면서 가장 긴 것의 길이를 출력한다.