Knuth-Morris-Pratt
Time Limit: 1000 MSMemory Limit: 10000 KB

Description

给定文本串s与模式串t,求s中是否有子串t。

Input

第一行输入T(T<=100)表示有T组数据。每组数据包含两行字符串,即为s、t,长度不大于100000。

Output

输出T行整数,若s中不存在子串t输出-1,否则输出t在s中第一次出现的位置。

Sample Input

3
ababa
aba
abcabda
abda
abcabda
daba

Sample Output

0
3
-1
Submit Your Code                        Discuss



苏ICP备2022026913号-1