void GetFail(int *P, int *f)
{
    f[0] = f[1] = 0;
    int m = strlen(P);
    for (int i = 1; i < m; i++)
    {
        int j = f[i];
        while (j && P[j] != P[i]) j = f[j];
        f[i + 1] = (P[j] == P[i] ? j + 1 : 0);
    }
}
 
void KMP(int *T, int *P, int *f)
{
    GetFail();
    int cnt = 0;
    int n = strlen(P), m = strlen(T);
    int j = 0;
    for (int i = 0; i < m; i++)
    {
        while (j && P[j] != T[i]) j = f[j];
        if (P[j] == T[i]) j++;
        if (j == n) return i - j + 1;
    }
    return cnt;
}