1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//http://hihocoder.com/contest/hiho3/problem/1
#include<cstdio>
#include<cstring>
using namespace std;
char str[1000009];
char p[10009];
int next[10009];
int main(void)
{
    int i,j,cases;
    scanf("%d", &cases);
    while(cases--)
    {
        scanf("%s", p);
        scanf("%s", str);
        
        int m = strlen(p);
        int n = strlen(str);
        
        next[0] = 0;
        for(i=1,j=0; i<m; ++i)
        {
            while(j>0 && p[j]!=p[i])
                j = next[j-1];
            if(p[j]==p[i])
                ++j;
            next[i] = j;
        }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX