pstring
All texts must be censored, especially those with revolutionary messages. You don't agree with this, but you have no choice: you have to write a program for censoring a given text. But you have decided to alter the text the least you can.
Task
Given a text and a forbidden message as two strings, write a program that will calculate the minimum number of characters to be removed from the initial text in order to obtain a text that does not contain the forbidden message as a subsequence.
Input data
Input file pstring.in contains on the first line the text to be censored and on the second line the forbidden message. Both text and forbidden message contain only lower case letters.
Output data
Output file pstring.out will have a single line containing a single number representing the minimum number of characters to be removed from the text.
Constraints
| pstring.in | pstring.out | Explicatie | pstring.in | pstring.out | Explicatie |
| wewantarevolutionforevolution revolution |
2 | For example, we can remove the two letters r | ababaa aba |
1 | We remove the second letter a. |
Time limit: 0.25 seconds/test
Memory limit: 65 MB, containing stack memory 1 MB.
Emilian Miron
University of Bucharest
Faculty of Mathematics and Informatics
Contact: emilian.miron@gmail.com