13751375 SUSTech Online Judge
Problem 1375 --[Hard] Cryptography

1375: [Hard] Cryptography

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 750  Solved: 206
[Submit][Status][Web Board]


Special spy Oken was caught by the defenders of Narnal country. Before he got caught, Oken tries to send a half-encrypted message to his friend, Secsip. However, due to the obstruction of Amayama, some part of the message was broken. Secsip knows that Oken's original message is a string, and he also knows the first half of the original message is an encryption of the second half using substitution cipher. The substitution cipher is a method of encrypting which replaces each letter in a string to another corresponding fixed letter in a bijection table which is known by Secsip. Now, Secsip receives the broken message, and he knows a suffix (which length could be 0) of the second half of the original message has been lost.  He wishes to recover this lost suffix as short as possible.  

A suffix of a string is a substring which ends with the last letter.


The first line is the code table for the substitution cipher, which contains 26 letters representing the encrypted letter for each letter in lexicographical order. 

The second line is a string which is the Oken's broken message. The length of the string is no longer than 500000.

All letters in this problem is in lowercase. 


An integer which stands the length of second half of Oken's original message with the lost suffix as short as possible.

Sample Input

b c d e f g h i j k l m n o p q r s t u v w x y z a

Sample Output



For the sample input, the strategy which can recover the second half of the original message as short as possible is to add a "d" at the end of the broken message, so that the second half "abcd" can be encrypted to the first half "bcde" using the given encryption table.