P8085 [COCI 2011/2012 #4] KRIPTOGRAM

现有一段明文和一部分密文。明文和密文都由英文单词组成，且密文中的一个单词必然对应着明文中的一个单词。 求给出的密文在明文中可能出现的最早位置。

第一行，若干个英文单词和一个 \$，表示明文。 第二行，若干个英文单词和一个 \$，表示密文。 每行末尾的 \$ 用于表示该行结束。数据保证没有多个 \$ 出现在同一行的情况。

输出密文在明文中可能出现的最早位置，即密文的第一个单词在明文中可能出现的最早位置。

**【数据规模与约定】** - 对于 $100\%$ 的数据，明文和密文所对应字符串的长度不超过 $10^6$，输入的单词均由小写字母组成。 **【提示与说明】** **题目译自 [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_。** **本题分值按 COCI 原题设置，满分 $140$。**