PSTRING  Remove The String
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
Buda IM (retired):
20120818 10:18:25
O( X*Y ), is just fine using bottom up, recursion will TLE. 

Jose Luis Castrillon Garrido:
20120428 22:24:12
O(length(X)*length(Y)) is getting TLE, is expected to implement another algorithm? 

cherudim:
20110203 04:43:28
Isn't it bbaa? Last edit: 20141017 16:51:26 

David Gómez:
20100722 03:15:49
If we remove the char 'c' from bbcaa, will the resulting string be bbaa or bb aa? 
Added by:  Hoang Hong Quan 
Date:  20060117 
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 