KMP 板子。自己看参考资料吧，这里供上代码：

#include<bits/stdc++.h>
using namespace std;
string s,t;
int n,m,ne[1111],q,ans,le;
int main(){
	while(true){
		memset(ne,0,sizeof(ne)),q=0,ans=0,le=0;
		cin>>s;
		if(s=="#") return 0;
		cin>>t;
		n=s.length(),m=t.length();
		s='0'+s,t='0'+t;
		for(int i=2;i<=m;i++){
			while(q&&t[q+1]!=t[i]) q=ne[q];
			if(t[q+1]==t[i]) q++;
			ne[i]=q;
		}
		q=0;
		for(int i=1;i<=n;i++){
			while(q&&t[q+1]!=s[i]) q=ne[q];
			if(t[q+1]==s[i]) q++;
			if(q==m&&i>=le) ans++,le=i+m;
		}
		printf("%d\n",ans);
	} 
}