Рекламный щит

시간 제한2초메모리 제한1024 MB

요약

문자열 s에서 잘라낸 조각을 순서대로 이어 붙여 t를 만들 때 필요한 최소 조각 수를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 이분 탐색, 문자열
정답자: 아직 제출이 없습니다

문제

Остап Бендер, великий комбинатор, решил податься в рекламный бизнес. Теперь он делает рекламные щиты. И Остап понимает, что куда дешевле взять старый щит, вырезать из него ненужные куски и получить новый.

Рекламный щит представляет собой табличку с лозунгом. Остап придумал новый лозунг, который можно получить из старого, путем выпиливания нескольких кусков из старого и склеивания этих кусков в том же порядке. К сожалению, места склейки нелицеприятно выглядят, поэтому Остап хочет уменьшить количество кусков, из которых собирается новый щит. Помогите Остапу подсчитать минимальное количество кусков, необходимое для получения нового щита.

입력

В первой строке входного файла дана строка $s$ , длины $n$ ( $1 \le n \le 10^5$ ) --- лозунг на первом щите, состоящий из маленьких английских букв. Во второй строке входного файла дана строка $t$ , длины $m$ ( $1 \le m \le 10^5$ ) --- лозунг, который хочет получить Остап.

출력

В единственной строке выходного файла выведите минимальное количество кусков, из которых собирается новый щите. Гарантируется, что ответ не превышает 10.

예제2

예제 1
입력
```
buyourchairs
yourhairs
```
예상 출력
```
2
```
예제 2
입력
```
goldencow
old
```
예상 출력
```
1
```