題目鏈接：點擊查看

題目大意：首先規定同構字符串，若字符串s和字符串t互為同構字符串，則必須滿足：

兩個字符串長度相同

s中的字符種類數與t中的字符種類數相同

s中的每一個字母在t中都有對應，且必須是一對一的映射關系

舉個很簡單的例子，wwaaa和aaccc是同構字符串，aababc和bbcbcz也是同構字符串

現在給出m個詢問，每次詢問給出 x y len，問長度為len，分別以 x 和 y 為起點的字串是否互為同構字符串

題目分析：一開始沒想到怎么去做，提示是哈希了之后也沒有什么很好的辦法，看了題解后感覺好巧妙的方法，真的算是學到了

回到這個題目上來，因為每個字母都是相對獨立的關系，所以我們對于26個字母進行哈希，也就是在讀入字符串后，預處理出Hash[i][j]，表示位置為 i ，當前字母為 j 的哈希值是多少，這樣預處理后，每次詢問我們只需要對于子串?x 的每一個字母從子串 y 中找到一個不矛盾的映射關系就行，如果26個字母全部都能找到映射關系，且不沖突，則說明互為同構串

還是感覺直接看代碼思路可能會比較清晰一點

最后說一點就是，對于單哈希來說，我一直使用的base=131，mod=ull_max會被hack掉。。不過用base=2333333，mod=999999998就能順利AC，那以后寫哈希就換成用這一套基數吧

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;const int base=2333333;const int mod=999999998;string s;int n,m;ull Hash[N][26],f[N];int nx[N][26],pos[26];//nx[i][j]:包含第i個位置在內，后面首次出現字母j的位置 void init() {f[0]=1;for(int i=1;i<=n;i++)//預處理出每個字母的哈希值{f[i]=f[i-1]*base%mod;for(int j=0;j<26;j++)Hash[i][j]=(Hash[i-1][j]*base+(s[i]==char(j+'a')))%mod; //這里的每一位哈希值非零即一，用來表示當前位置是否為當前字母}for(int j=0;j<26;j++)pos[j]=n+1;for(int i=n;i>=1;i--)//預處理出nx數組，簡單dp{pos[s[i]-'a']=i;for(int j=0;j<26;j++)nx[i][j]=pos[j];} }ull get_hash(int l,int r,int alpha) {return (Hash[r][alpha]-Hash[l-1][alpha]*f[r-l+1]%mod+mod)%mod; }bool solve(int x,int y,int len,int alpha) {int pos=nx[x][alpha];//找到在x中對應的字母if(pos>x+len-1)//如果沒找到說明x中不存在這個字母，直接返回truereturn true;pos+=y-x;//映射到y中的字母去return get_hash(x,x+len-1,alpha)==get_hash(y,y+len-1,s[pos]-'a');//判斷哈希值是否相等 }bool check(int x,int y,int len) {for(int j=0;j<26;j++)//枚舉子串x中的每個字母是否有沖突 if(!solve(x,y,len,j))return false;return true; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%d%d",&n,&m);cin>>s;s=" "+s;init();while(m--){int x,y,len;scanf("%d%d%d",&x,&y,&len);if(check(x,y,len))puts("YES");elseputs("NO");}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 985F Isomorphic Strings(字符串哈希)的全部內容，希望文章能夠幫你解決所遇到的問題。

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