题目链接：点击查看
题目大意：首先规定同构字符串，若字符串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;
}