Function main

String Algorithms/String Matching.cpp:20–51

}

int main(){
    scanf("%s %s", S, T);
    N = (int) strlen(S); M = (int) strlen(T);

    if(M > N){
        printf("0\n");
        return 0;
    }

    for(int p = 0; p < numP; p++){
        pw[p][0] = 1;
        for(int i = 1; i < maxN; i++)
            pw[p][i] = (pw[p][i-1] * prime[p]) % MOD;
    }

    for(int i = 0; i < M; i++){
        for(int p = 0; p < numP; p++){
            sh[p] = (sh[p] + (S[i] - 'a' + 1) * pw[p][M-i-1]) % MOD;
            th[p] = (th[p] + (T[i] - 'a' + 1) * pw[p][M-i-1]) % MOD;
        }
    }

    if(hashes_equal())  cnt++;
    for(int i = M; i < N; i++){
        for(int p = 0; p < numP; p++){
            sh[p] = (sh[p] * prime[p] - (S[i-M] - 'a' + 1) * pw[p][M]) % MOD;
            sh[p] = (sh[p] + (S[i] - 'a' + 1) + MOD) % MOD;
        }
        if(hashes_equal())  cnt++;
    }
    printf("%d\n", cnt);
}