#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<cmath>#include<queue>#include<algorithm>#define FOR(i, x, y) for(int i=(x); i<=(y); i++)#define rFOR(i, x, y) for(int i=(x); i>=(y); i--)#define sqr(x) ((x)*(x))#define MS(x, y) memset(x, y, sizeof(x))#define oo 0x7f7f7f7f#define MAXN 512005using namespace std;int N, M;char a[MAXN], b[260];int P[260];int next[MAXN], pre[MAXN];void init(){ N = strlen(a + 1); M = strlen(b + 1); int i, j; MS(P, 0); MS(next, 0); MS(pre, 0); j = 0; FOR(i, 2, M) { while(j && b[j + 1] != b[i]) j = P[j]; if(b[j+1] == b[i]) ++j; P[i] = j; } FOR(i, 1, N) { pre[i] = i - 1; next[i] = i + 1; } pre[0] = 0; next[0] = 1;}void dele(int i){ next[pre[i]] = next[i]; pre[next[i]] = pre[i];}void solve(){ int ans = 0; int j = 0; for(int i = 1; i <= N; i = next[i]) { while(j && b[j + 1] != a[i]) j = P[j]; if(b[j + 1] == a[i]) ++j; if(j == M) { ++ans; j = 0; FOR(k, 1, M) { dele(i); i = pre[i]; } FOR(k, 1, M) if(i) i = pre[i]; else break; } } printf("%dn", ans);}int main(){ while(scanf(" %s %s", b+1, a+1) != EOF) { init(); solve(); } return 0;}
