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

## 1375: [Hard] Cryptography

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 733  Solved: 199
[Submit][Status][Web Board]

## Description

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.

## Input

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.

## Output

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
bcdeabc

## Sample Output

4

## HINT

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.

[Submit][Status]