题目描述

现有一段明文和一部分密文。明文和密文都由英文单词组成，且密文中的一个单词必然对应着明文中的一个单词。

求给出的密文在明文中可能出现的最早位置。

输入格式

第一行，若干个英文单词和一个 $\texttt \$$，表示明文。

第二行，若干个英文单词和一个 $\texttt \$$，表示密文。

每行末尾的 $\texttt \$$ 用于表示该行结束。数据保证没有多个 $\texttt \$$ 出现在同一行的情况。

输出格式

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

a a a b c d a b c $
x y $

3

xyz abc abc xyz $
abc abc $

2

a b c x c z z a b c $
prvi dr prvi tr tr x $

3

提示

【数据规模与约定】

• 对于 $100\%$ 的数据，明文和密文所对应字符串的长度不超过 $10^6$，输入的单词均由小写字母组成。

【提示与说明】

题目译自 COCI 2011-2012 CONTEST #4 Task 6 KRIPTOGRAM。

本题分值按 COCI 原题设置，满分 $140$。