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 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.


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




hide comments
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

Muhammad Rifayat Samee (Sanzee): 2015-04-23 22:20:29

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

Luka Chumburidze: 2015-02-18 20:19:10

Jose Luis Castrillon Garrido try to use

Buda IM (retired): 2012-08-18 10:18:25

O( |X|*|Y| ), is just fine using bottom up, recursion will TLE.

Jose Luis Castrillon Garrido: 2012-04-28 22:24:12

O(length(X)*length(Y)) is getting TLE, is expected to implement another algorithm?

Added by:Hoang Hong Quan
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