思路

多组模式在文本中出现次数，重叠也计数；模式1万文本100万，匹配后按前缀函数回退。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
vector<int> prefix(const string&s){vector<int>p(s.size());for(int i=1;i<(int)s.size();i++){int j=p[i-1];while(j&&s[i]!=s[j])j=p[j-1];if(s[i]==s[j])j++;p[i]=j;}return p;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while(t--){string p,s;cin>>p>>s;auto a=prefix(p);int j=0,ans=0;for(char c:s){while(j&&p[j]!=c)j=a[j-1];if(p[j]==c)j++;if(j==(int)p.size()){ans++;j=a[j-1];}}cout<<ans<<'\n';}}