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
|
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? |
|
cherudim:
2011-02-03 04:43:28
Isn't it bbaa? Last edit: 2014-10-17 16:51:26 |
|
David Gómez:
2010-07-22 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: | 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 |
RSS