29243번 - Рекламный щит 다국어

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

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

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

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