P8085 [COCI 2011/2012 #4] KRIPTOGRAM

You are given a piece of plaintext and a part of ciphertext. Both the plaintext and the ciphertext consist of English words, and each word in the ciphertext must correspond to a word in the plaintext. Find the earliest possible position where the given ciphertext could appear in the plaintext.

The first line contains several English words and a `$`, representing the plaintext. The second line contains several English words and a `$`, representing the ciphertext. The `$` at the end of each line indicates the end of that line. The testdata guarantees that there will not be multiple `$` symbols in the same line.

Output the earliest possible position where the ciphertext could appear in the plaintext, i.e., the earliest possible position of the first word of the ciphertext in the plaintext.

**Constraints** - For $100\%$ of the testdata, the total length of the strings corresponding to the plaintext and the ciphertext does not exceed $10^6$. All input words consist of lowercase letters. **Hints and Notes** **This problem is translated from [COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #4](https://hsin.hr/coci/archive/2011_2012/contest4_tasks.pdf) _Task 6 KRIPTOGRAM_.** **The score of this problem follows the original COCI settings, with a full score of $140$.** Translated by ChatGPT 5