Square만들기 timer 1s memory - MB

문자열이 같은 2개의 문자열을 이어놓은 형태일 경우 이를 square라 한다. abcabc나 aaaa의 경우는 sqaure이지만 aaa, abcab, defgh는 square가 아니다.

문자열 S가 주어질 때 다음의 3가지 연산을 이용하여 S를 sqaure로 만들려고 한다.

1. S의 한 문자를 다른 문자로 바꾼다. 2. S의 한 문자를 지운다. 3. S의 맨 앞과 맨 끝을 포함해 임의의 위치에 새로운 문자를 집어 넣는다.

예를 들어 S = "abaca"일 경우 1,2,3 중 하나의 연산을 적용하였을 때, abeca, baca, abafca, gabaca로 바꿀 수 있다. bac를 만들기 위해서는 최소 2번의 연산을 적용하여 만들 수 있고, dafg의 경우에는 최소 4번의 연산을 적용해야한다. 그리고 빈 문자열을 만들기 위해서는 최소 5번의 연산을 적용해야한다.

S가 주어졌을 때 S를 square인 문자열로 바꾸기 위해 사용하는 연산의 수를 최소화 하는 프로그램을 작성하라.