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
xxbloodysantaxx:
20160312 10:16:13
There are multiple Test Cases my solution was correct from the beginning!


invoker_war:
20151029 11:10:37
how many test cases are there? 

hnvahidi:
20150904 13:37:30
are x and y nonempty strings?


Petar Nyagolov:
20150804 13:29:51
My 100th :P Nice problem! :) 

osama:
20150609 10:00:10
any hint please this my code


Muhammad Rifayat Samee (Sanzee):
20150423 22:20:29
are all the char from 'a' to 'z' ?? 

Luka Chumburidze:
20150218 20:19:10
Jose Luis Castrillon Garrido try to use


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 
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 PERL 6 VB.net 
Resource:  A contest of Romanian 