농부 존은 그의 이웃과 끔찍한 싸움을 벌이고 있었고, 그 이웃에게 익명으로 나쁜 협박편지를 보내고 싶어한다. 따라서 농부 존이 해왔던 것처럼 그는 인쇄물에서 글자를 오려서 하나의 편지에 붙여서 한 장 짜리 협박편지를 만들 계획이다. 그는 '음메타임즈'라는 이름의 잡지의 최근 부수를 무한 권 가지고 있다.
각각의 '음메타임즈'는 N (1 <= N <= 50000) 개의 대문자를 가지고 있으며 글자들은 긴 연속된 문자열들로 이루어져있다. (비록 읽을 때는 끊어서 읽을지라도 말이다.) 또한, 그가 보내고 싶어하는 문자열들이 있다. 그 문자열들은 다소 짧은 문자열로 이루어져있다.
그는 평소에 게으르기 때문에 그가 원하는 편지를 만들기 위해 최소한의 가위질을 하고 싶어한다. 그는 아주 멋진 가위들을 가지고 있어서 잡지에서 원하는 만큼을 한 번에 오려낼 수 있다. 또한 단어를 만들기 위해 각각의 글자들을 오려낼 필요가 없단것을 깨달았기 때문에 그는 가위질을 적게 할 수 있을 것이다. 그가 M (1 <= M <= 50000) 길이의 편지를 만들기 위해 필요한 최소한의 가위질은 몇 번인지 구하는 것이 당신이 할 일이다.
다음의 예시를 보자. 잡지의 내용은 다음과 같고,
THEQUICKBROWNFOXDOGJUMPSOVERTHELAZYDOG
농부 존이 원하는 내용은 다음과 같다.
FOXDOGDOG
그렇다면 농부 존은 FOXDOG 와 DOG 를 오려내서 원하는 내용을 만들 수 있다. (같은 내용의 잡지는 무한 권 있다.) 따라서 농부 존은 최소 두 번의 가위질만 필요하다.
입력 38 9 THEQUICKBROWNFOXDO GJUMPSOVERTHELAZYDOG FOXDOG DOG 출력 2
출처: usaco 2010 DEC gold 번역: KangJ