목걸이

소 베시(Bessie)는 알파벳 소문자가 하나씩 적힌 돌 $N$개를 한 줄로 늘어놓아 멋진 목걸이를 만들려고 합니다. 돌을 놓인 순서대로 읽으면 길이 $N$의 문자열이 됩니다.

베시는 자기 물건을 소중히 여겨서, 같은 외양간 반대편에 사는 다른 소와 이 목걸이를 나눠 쓰고 싶지 않습니다. 그 소의 이름은 길이 $M$의 문자열인데, 만약 이 길이 $M$의 문자열이 목걸이 문자열 안에 연속된 부분 문자열로 나타나면 그 소가 목걸이를 자기 것으로 착각할 수 있습니다. 그래서 베시는 목걸이에서 돌 몇 개를 빼내어 다른 소의 이름이 부분 문자열로 나타나지 않게 하려고 합니다. (돌을 빼내면 남은 돌들이 원래 순서를 유지한 채 이어져 새로운 목걸이 문자열을 이룹니다.)

베시가 빼내야 하는 돌의 최소 개수를 구하세요.

• 첫째 줄: 베시의 처음 목걸이를 나타내는 길이 $N$의 문자열. 각 문자는 a부터 z 사이입니다.
• 둘째 줄: 외양간에 사는 다른 소의 이름을 나타내는 길이 $M$의 문자열. 마찬가지로 a부터 z 사이의 문자로 이루어집니다.

• 첫째 줄: 다른 소의 이름이 부분 문자열로 나타나지 않도록 베시의 목걸이에서 빼내야 하는 돌의 최소 개수.

• $1 \le M \le N \le 10000$
• $M \le 1000$
• 목걸이와 이름의 모든 문자는 a부터 z 사이의 소문자입니다.