KMP

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include <vector>

using namespace std;

int m,n;
int ans;
char a[10007],b[10007];
int nex[10007];
void getnext()//求子串的next数组
{
	int i = 1, j = 0;
	while(i < m)
	{
		if(j == 0 && b[i] != b[j])
		{
			nex[i] = 0;
			i ++;
		}
		else if(j > 0 && b[i] != b[j])
			j = nex[j-1];
		else
		{
			nex[i] = j + 1;
			i ++; 
			j ++;
		}
	}
}
int kmp()
{
	int i = 0,j = 0;
	while(i < n && j < m)
	{
		if(j == 0 && a[i] != b[j])
			i ++;
		else if(j > 0 && a[i] != b[j])
			j = nex[j-1];
		else
		{
			i ++; 
			j ++;
		}//查找相同部分
		if(j == m)
		{
			ans++;
			j=0;//求不重叠的子串个数，若判断有没有子串，直接输出ans,若重叠的子串个数，不用对j赋值，输出ans,若输出起始位置，i-j+1;
		}
	}
		return ans;
}
int main()
{
	while(~scanf("%s",&a)&&a[0]!='#')
	{
		scanf("%s",&b);
		ans=0;
		m=strlen(b);
		n=strlen(a);
		getnext();
		kmp();
		printf("%d\n",ans);
	}
	return 0;
}