Question

Paste Reduction Some keys in Codu's computer keyboard are not working. Fortunately for Codu, these characters are present in a previously existing text file. He wants to write a paragraph which involves typing those characters whose keys are defunct in Codu's keyboard. Only option left for Codu is to copy-paste those characters from the previously existing text files. However, copy-pasting keys is a laborious operation since one has to switch windows and also previously copied items are lost once a new set of characters are copied. Hence, Codu wants to minimize the number of times he needs to copy-paste from that text file. Fortunately there can be situations where previously copied characters are readily available for pasting. Help Codu devise a method to minimize the number of times a paste operation is needed, given - the text he intends to type and the faulty keys Constraints 0 < Length of paragraph <= 1000 characters 0 < number of faulty keys in keyboard <= 36 Only a to z and 0 to 9 keys can be faulty. Input paragraph will not contain any upper-case letter. Input First line contains a paragraph that is be to be written. Second line contains a string. This string has to be interpreted in the following fashion All characters in that string correspond to faulty keys That string is available for copy as-is from the other text file that Codu is referring Also, individual characters can always be copied from the same text file Output Single integer denoting minimum number of copy operations required Time Limit 1 Examples Example 1 Input supreme court is the highest judicial court su Output 4 Explanation Codu will first paste su from the file when typing characters su in the word supreme. In the second instance, Codu will need to copy character u and paste it when typing character u in the word court. In the third instance, Codu will need to copy character su and paste su when typing character s in the word is. Codu will back track using the left arrow key and type the characters "the highe". In the fourth instance, Codu will again paste su. The overall string typed until this moment is "supreme court is the highesuu". Codu will then back track again using left arrow key and type characters "t j". At this point the typed string is "supreme court is the highest juu". Cursor is after character j. Codu will use right arrow key and now the cursor will be after ju. Codu will now type "udicial co". String typed till this point is "supreme court is the highest judicial cou". Cursor is after character o. Codu will use right arrow and the cursor will be after character u. Finally Codu will type "rt". Final string - "supreme court is the highest judicial court" - is thus fully typed. Here, the number of paste operations are 4.

Answer 1

Answer:

Thanks for your information