PSTRING - Remove The String

no tags 

Given two strings X and Y, your task is find the minimum number of characters to be removed from X in order to obtain a string X' that does not contain Y as a substring.

Input

Input contains some test cases. Each test cases contains two lines, First is X and second is Y. Length of X <= 10000, Length of Y <= 1000.

Output

For each test cases, You should output exactly one integer is the minimum number of characters to be remove

Example

Input:
ababaa
aba

Output:
1

hide comments
zerotwo: 2020-05-09 19:17:32

pay attention that there are multiple test cases

chodermal: 2019-12-30 22:34:45

abba ne harmonium baja dala

Shubhojeet Chakraborty: 2018-08-07 11:11:08

Phew, nice concept,better time limit,made too many silly mistakes,glad to AC this.Kudos to the setter.

MD. Shakhawat hossain sajal: 2017-11-13 19:01:11

It is abbaa.

Last edit: 2017-11-13 19:01:28
xxbloodysantaxx: 2016-03-12 10:16:13

There are multiple Test Cases my solution was correct from the beginning!

-___-

Last edit: 2016-03-12 10:19:04
invoker_war: 2015-10-29 11:10:37

how many test cases are there?

hnvahidi: 2015-09-04 13:37:30

are x and y non-empty strings?
logically it should be

Petar Nyagolov: 2015-08-04 13:29:51

My 100th :P Nice problem! :)

osama: 2015-06-09 10:00:10

any hint please this my code
<snip>

Last edit: 2022-10-13 22:11:58
Muhammad Rifayat Samee (Sanzee): 2015-04-23 22:20:29

are all the char from 'a' to 'z' ??


Added by:Hoang Hong Quan
Date:2006-01-17
Time limit:1.265s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:A contest of Romanian