Notes/Sunday.cpp at master · AgateLee/Notes · GitHub

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstring>
using namespace std;

char P[10002];
char T[1000002];
char pos[256];

int Sunday()
{
    int len = strlen(T), len0 = strlen(P),
        i, j, sum, next;

    memset(pos, -1, sizeof(pos));

    for(i = len0 - 1; i >= 0; i--)
    {
        if(pos[P[i]] == -1)
            pos[P[i]] = i;
    }

    i = j = sum = 0;

    while(i < len - len0)
    {
        if(T[i] == P[j])
        {
            i++;
            j++;

            if(j == len0)
            {
                i = i - len0 + 1;
                j = 0;
                sum += 1;
            }
        }
        else
        {
            next = i - j + len0;
            if(P[T[next]] != -1)
            {
                i = next - pos[T[next]];
            }
            else
            {
                i = next + 1;
            }

            j = 0;
        }
    }

    return sum;
}

int main()
{
    int N;
    scanf("%d", &N);

    while(N --)
    {
        scanf("%s %s", P, T);
        printf("%d\n", Sunday());
    }

    return 0;
}