正題

題目鏈接:http://noip.ybtoj.com.cn/contest/105/problem/2

---

題目大意

一個$01$串，$q$個詢問，每次詢問有多少個長度為$m$的子串$01$個數與給出的$01$串$T$相同

---

解題思路

因為詢問串的總長與$n$同級，所以考慮根號分治
將詢問的$T$串長度分為兩部分。對與大于$\sqrt{n}$的，我們直接暴力，因為這樣的串的個數不會超過$\sqrt{L}$個，所以時間復雜度是$O(n\sqrt{L})$的。對與小于$\sqrt{n}$的，我們提前預處理，時間復雜度$O(n\sqrt{n})$

所以時間復雜度是$O(n\sqrt{n})$的

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=2e5+10; int n,m,a[N],v[510][N]; char s[N],t[N]; int main() { // freopen("similar.in","r",stdin); // freopen("similar.out","w",stdout);scanf("%s",s+1);n=strlen(s+1);scanf("%d",&m);for(int i=1;i<=n;i++)a[i]=a[i-1]+s[i]-'0';int T=sqrt(n);for(int i=1;i<=T;i++)for(int j=0;j<=n-i;j++)v[i][a[j+i]-a[j]]++;while(m--){scanf("%s",t+1);int l=strlen(t+1),k=0;for(int i=1;i<=l;i++)k+=(t[i]-'0');if(l>T){int ans=0;for(int i=0;i<=n-l;i++)ans+=((a[i+l]-a[i])==k);printf("%d\n",ans);}else printf("%d\n",v[l][k]);} }

總結

以上是生活随笔為你收集整理的YbtOJ#20072-[NOIP2020模拟赛B组Day6]相似子串【根号分治】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。