题目链接
这道题的本质思想也是暴力
但是是有技巧的暴力
首先用到了hash算法
将母串的所有情况列出来，然后存到数组里面
对于子串，查询是否有该情况，一般用map，但是map太慢，这里用unordered_set
unordered_set用法
#include<bits/stdc++.h> #define debug(a) cout << #a << " " << a << endl #define LL long long #define ull unsigned long long #define PI acos(-1.0) #define eps 1e-6 const int N=1e6+7; const int base=233; using namespace std; unordered_set<ull> s; char s1[N],s2[N]; ull p[N]; int len_a,len_b; void init() { len_a=strlen(s1+1); ull Hash=0; p[0]=1;//p数组记录单位 for(int i=1; i<=len_a; i++) { Hash=Hash*base+s1[i]-'0';//计算总的哈希值 p[i]=p[i-1]*base; } s.insert(Hash); for(int i=1; i<=len_a; i++) { Hash=(Hash-(s1[i]-'0')*p[len_a-1])*base+s1[i]-'0';//将所有情况存储起来 s.insert(Hash); } } int main () { //yyy_3y //freopen("1.in","r",stdin); scanf("%s",s1+1); init(); int n; scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%s",s2+1); len_b=strlen(s2+1); ull Hash=0; ull ans=0; for(int i=1; i<=len_a; i++) { Hash=Hash*base+s2[i]-'0'; } if(s.count(Hash)) ans++; for(int i=len_a+1; i<=len_b; i++) { Hash=(Hash-(s2[i-len_a]-'0')*p[len_a-1])*base+s2[i]-'0'; if(s.count(Hash)) ans++; } printf("%llu\n",ans); } return 0; } 代码转自：http://blog.csdn.net/yyy_3y/article/details/79546003