원형스탬프 timer 1s memory 64MB

문구용품을 생산하는 만수네 공장에서는 업체마다 스탬프를 주문받아서 제작하다보니 대량생산이 불가능하고 단가도 높기 때문에 대량생산을 통해 단가도 낮추고 매출도 올릴수 있는 획기적인 시스템을 개발하였다.

그 방법은 원형의 스탬프를 미리 만들어 놓고 거기에 빅데이터를 이용하여 주로 많이 사용되는 글자들을 중심으로 미리 배치해 놓았다가 주문이 들어오면 필요한 글자들을 제외한 나머지 글자들을 쉽게 제거하고 필요한 글자들 사이의 공백을 간단하게 제거하여 선택된 글자들을 모아 놓을 수 있게 제품을 개발한 것이다.

예를 들어 “IAKESSEBAISEKISS”라는 문자열로 다음과 같이 기본 스탬프를 미리 만들어 놓았다가

“KISE” 라는 스탬프의 주문이 들어오면 오른쪽으로 돌아가면서 차례대로 4자를 선택한 후 나머지를 모두 제거하고 남은 4자의 간격을 없애게 되면 아래와 같은 스탬프가 완성되는 것이다.

이 공장에서는 가능하면 많은 주문에 대처할 수 있는 문자열을 기본 스탬프로 선정하기 위해 글자를 선택할 수 있는 경우의 수가 몇가지나 되는지를 확인하여야 한다.

예를 들어 위의 예제의 경우 아래와 같이 18가지의 선택이 가능하다. 

기본 문자열과 주문 문자열이 주어지면 주문 문자열의 순서대로 문자를 선택할 수 있는 방법이 몇가지인지 경우의 수를 구하는 프로그램을 작성하라.