学密码学一定得学程序

Description

曾经，ZYJ同学非常喜欢密码学。有一天，他发现了一个很长很长的字符串S1。他很好奇那代表着什么，于是神奇的WL给了他另一个字符串S2。但是很不幸的是，WL忘记跟他说是什么意思了。这个时候，ZYJ不得不求助与伟大的ZP。ZP笑了笑说，这个很神奇的，WL的意思是只要你找到她给你的字符串在那个神奇的字符串的位置，你就会有神奇的发现。ZYJ恍然大悟，原来如此，但是悲剧来了，他竟然不知道怎么找。。。。是的，很囧是不是。所以这时候就需要化身为超级玛丽亚的你现身了，告诉他吧。。。。。。
Input

首先输入一个n。表示有n组测试数据。

每组测试数据有两行。

第一行为字符串S1，长度不大于1000000。

第二行为字符串S2，长度不大于10000,并且长度不小于2。
Output

输出S2在S1的位置。如果有多个位置，只输出第一个位置。

如果找不到，就输出“::>_<::“（不输出双引号）。
Sample
Input

1

ASDFGDF

DF

Output

3

Hint

#include <bits/stdc++.h>

using namespace std;

char s[1000010], p[1000010];
int Next[1000010];

void get_next()
{
   int j = -1, k = 0;
   Next[0] = -1;
   int len = strlen(p);
   while(k < len)
   {
       if(j == -1 || s[j] == s[k])
       {
           j++;
           k++;
           Next[k] = j;
       }
       else j = Next[j];
   }
}
void kmp()
{
   int i = 0, j = 0;
   int slen = strlen(s);
   int plen = strlen(p);
   while(i < slen && j < plen)
   {
       if(j == -1 || s[i] == p[j])
       {
           i++;
           j++;
       }
       else j = Next[j];
   }
   if(j == plen)
       printf("%d\n", i - j + 1);
   else printf("::>_<::\n");
}
int main()
{
   int n;
   cin >> n;
   while(n--)
   {
       cin >> s >> p;
       get_next();
       kmp();
   }
   return 0;
}