OI题库

【问题描述】

小x收到了一份加密的英语考试作文答案。于是他迫切需要将其解密，在经历了很多磨难之后，他得到了部分原文，注意，只是部分原文。

为了破解加密的作文，小x需要做的第一件事情就是找到原文在加密作文中可能第一次出现的位置。加密的作文中的单词和原文中的单词必须是一一对应，每个单词用空格隔开。

比如加密的作文是：“a a a b c d a b c”这里包含了9个用空格隔开的单词，部分原文是：“x y”，这里x和y是不一样的，而在加密的作文由第3个字符开始的两个单词也是不一样的，所以原文在加密作文中第一次可能出现的位置为3。

再给一个例子，加密的作文时：“a b c x c z z a b c”，部分原文是：“prvi dr prvi tr tr x”，那么部分原文第一次可能出现的位置是3，“prvi”对应“c”，“dr”对应“x”，依次类推。这里原文与加密后的单词肯定是一一对应。

现在小x要你帮助他完成这个任务。

【输入】

第一行是加密后的作文全文，全文的字符个数不会超过10^6个。每个单词用一个英文空格隔开，最后以一个单独的”$”结束，”$”不包含在文章中。

第二行是原文的部分句子，部分句子的字符个数不会超过10^6个。每个单词用一个英文空格隔开，最后以一个单独的”$”结束，”$”不包含在文章中。

保证字符都是小写字符，且都是一个空格隔开。这里的 10^6个字符上限不包含空格。

【输出】

一个整数，原文的部分句子在加密的作文中可能第一次出现的位置，这个位置就是加密作文中第一个单词所处在加密文章中位置。

数据保证有解。

【输入输出样例1】

kriptogram.in	kriptogram.out
a a a b c d a b c $ x y $	3

【输入输出样例2】

kriptogram.in	kriptogram.out
a b c x c z z a b c $ prvi dr prvi tr tr x $	3

【输入输出样例3】

kriptogram.in	kriptogram.out
xyz abc abc xyz $ abc abc $	2

【数据范围】 

   10% 数据保证 加密和原文单词数目 小于等于10

   20% 数据保证 加密和原文单词数目 小于等于1000

   100%数据如题目描述