21St Century Fruits 회사는 기존의 과일의 유전자를 다른 과일의 유전자에 옮겨서 새로운 과일을 만드는데 특화되어 있다. 이러한 시도는 대부분 좋은 결과를 얻지 못하지만 때때로는 두 과일의 맛을 합쳐놓은 새로은 품종의 과일이 나타난다.
이 경우 이 과일의 이름을 무엇으로 할까를 고민하게 되는데 , apple 과 pear 사이의 새로운 과일은 apple-pear 로 부를수도 있지만 흥미롭게 들리지는 않는다. 그래서 양 쪽 과일의 이름을 모두 포함하는 부분 문자열로 새로운 이름을 부여하기로 하였다.
예를 들어 , apple 과 pear 는 applear (APPLEar , apPlEAR ) 이런 성질을 가진 이 보다 더 짧은 문자열은 없다. 또한 cranberry 과 boysenberry 는 boysecranberry 혹은 craboysenberry
두가지 이름을 입력으로 받아서 이를 만족하는 최단 문자열을 만드는게 문제이다.
입력 apple peach 출력 appleach 입력 ananas banana 출력 bananas 입력 pear peach 출력 pearch
출처:Ulm Local 1999