Cod sursa(job #2579877)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 12 martie 2020 22:57:27
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 2000100;

int ans;
int lg1, lg2;
int pi_n[NMAX], pi_m[NMAX];
char N[NMAX], M[NMAX];

void cal_pi_n(){
    int k = 0;
    for(int i = 2; i <= lg1; i++){
        while(k > 0 && N[k + 1] != N[i])
            k = pi_n[k];
        if(N[k + 1] == N[i])
            k++;
        pi_n[i] = k;
    }
}

void cal_pi_m(){
    int k = 0;
    for(int i = 1; i <= lg2; i++){
        while(k > 0 && N[k + 1] != M[i])
            k = pi_n[k];
        if(N[k + 1] == M[i])
            k++;
        pi_m[i] = k;
    }
}

int main(){

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s %s", N + 1, M + 1);
    lg1 = strlen(N + 1);
    lg2 = strlen(M + 1);
    cal_pi_n();
    cal_pi_m();
    for(int i = 1; i <= lg2; i++)
        if(pi_m[i] == lg1)
            ans++;
    printf("%d", ans);


    return 0;
}