题目：http://www.gdfzoj.com/oj/contest/469/problems/1

 

样例解释：

子串Acad、cadA是cAda的子串

 

看到样例很容易想到桶。。。但300000太大了，于是可以换个方法，比如多用一个桶

#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;const int maxS=3000000;
int n,m;
char s1[maxS+5],s2[maxS+5];
int tong1[60],ss2[maxS+5],tong2[60];int main()
{int i,j,ans,t;freopen("a.txt","r",stdin);scanf("%d%d",&n,&m);scanf("%s",s1);scanf("%s",s2);memset(tong1,0,sizeof(tong1));memset(tong2,0,sizeof(tong2));for (i=0;i<n;i++)if (s1[i]>='a')tong1[s1[i]-'a'+26]++;elsetong1[s1[i]-'A']++;for (i=0;i<m;i++){if (s2[i]>='a')ss2[i]=s2[i]-'a'+26;elsess2[i]=s2[i]-'A';}ans=0;for (i=0;i<n;i++)//初始化 tong2[ss2[i]]++;for (i=0;i<=m-n;i++){t=0;for (j=0;j<52;j++)if (tong2[j]!=tong1[j]){t=1;break;}if (t==0)ans++;tong2[ss2[i]]--;//向后推进 tong2[ss2[i+n]]++;}printf("%d\n",ans);return 0;
}