正題

---

題目大意

長度為n的字符串，有q個詢問，求$[l～r]$這個區(qū)間的最小子串出現(xiàn)次數(shù)。

---

解題思路

這個就是一道坑題
我們可以發(fā)現(xiàn)如果有一個長度為2的子串，那么這個子串前面那一部分一定是更小的。
所以最小子串一定是一個字母，我們可以用前綴和瞎搞搞就好了。

---

code

#include<cstdio> #define N 1000010 using namespace std; int n,q,sum[N][26],l,r,t; char s[N]; int main() {scanf("%d",&t);for(int ti=1;ti<=t;ti++){scanf("%d%d",&n,&q);scanf("%s",s+1);for(int i=1;i<=n;i++)for(int j=0;j<26;j++)sum[i][j]=sum[i-1][j]+(s[i]=='A'+j);//前綴和for(int i=1;i<=q;i++){scanf("%d%d",&l,&r);for(int j=0;j<26;j++)if(sum[r][j]-sum[l-1][j]>0)//是否有這個字母{printf("%d\n",sum[r][j]-sum[l-1][j]);//輸出答案break;}}} }

總結

以上是生活随笔為你收集整理的nssl1186-字串数量【前缀和】的全部內容，希望文章能夠幫你解決所遇到的問題。

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