正題

題目鏈接:https://www.luogu.com.cn/problem/U142342?contestId=37784

---

題目大意

一個字符串，定義兩個字符串相似為用一些字母代替相同的字母后可以相同。

如$urbbr=groor$，$apple=abcde$

要求支持詢問一個字符串的兩個區(qū)間是否相似

---

解題思路

我們每個位置的$hash$值維護這個字母距離上一個與它相同的字母的距離，發(fā)現(xiàn)如果一個字母在這個區(qū)間里第一次出現(xiàn)，那么我們應該把它的$hash$值清$0$，所以我們可以直接枚舉區(qū)間的第一個字母然后減去它的$hash$值即可。

時間復雜度$O(26n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ull unsigned long long using namespace std; const int N=2e5+10; const ull p=1145141; int n,m,last[26],nxt[N][26];char s[N]; ull pw[N],h[N],f[N]; int get(int l,int r){ull ans=h[r]-h[l-1]*pw[r-l+1];for(int i=0;i<26;i++){if(nxt[l][i]<0||l+nxt[l][i]>r)continue;ans=ans-f[l+nxt[l][i]]*pw[r-l-nxt[l][i]];}return ans; } int main() {scanf("%d%d",&n,&m);scanf("%s",s+1);pw[0]=1;for(int i=1;i<=n;i++){int c=s[i]-'a';h[i]=h[i-1]*p+(f[i]=i-last[c]);pw[i]=pw[i-1]*p;last[c]=i;}memset(last,0,sizeof(last));for(int i=n;i>=1;i--){last[s[i]-'a']=i;for(int j=0;j<26;j++)nxt[i][j]=last[j]-i;}for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);if(get(x,x+z-1)==get(y,y+z-1))printf("YES\n");else printf("NO\n");} }

總結(jié)

以上是生活随笔為你收集整理的[2020.11.26NOIP模拟赛]询问【字符串hash】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。