ZOJ Problem Set - 3455
Nobita receives a letter from Shizuka. For the sake of security, the letter's content T is produced as follows, first the message is written, then the substitution cipher and transposition cipher is applied to the message. Finally, the encrypted message is inserted into another text.
Substitution cipher changes all occurrences of each letter to some other letter. Substitutes for all letters must be different. For example, after substitution cipher, the message "BBA" can become "AAC".
Transposition cipher applies some permutation to the letters of the message. For example, after applying the permutation (1, 3, 2), the second letter moves to the third place, the third letter moves to the second place, so the message "AAC" turns to "ACA".
For example, suppose the original message is "BBA", after substitution, it becomes "AAC", then after transposition, it becomes "ACA". Finally the encrypted message "ACA" is inserted into another text "CBC", after letter 'B', so the content of the letter is "CBACAC".
Nobita don't know what the original message is, but he guesses the message should be P. Now given the letter's content T and Nobita's guess P, you should determine if Nobita's guess is possible to be right.
There are multiple cases.
For each case, the first line is letter's content T, the second line is Nobita's guess P. P and T are strings consist of characters whose ASCII code is between 33 ('!') and 126 ('~'). The length of P and T is no more than 500000. P is guaranteed to be shorter than T.
OutputFor each case, if Nobita's guess is possible to be right, output "Yes", otherwise output "No". If the answer is "Yes", it should be followed by another line of integers which denote all the positions (0-based) of the message in the content.
CBACAC BBA ABCDE BBA
Yes 2 3 No
Author: ZHOU, Yilun
Contest: ZOJ Monthly, December 2010