Pagini recente » Cod sursa (job #3212028) | Cod sursa (job #654834) | Cod sursa (job #830511) | Cod sursa (job #1052106) | Cod sursa (job #2579877)
#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;
}