CodeForces985F:Isomorphic Strings (字符串&hash)

Stella981
• 阅读 801

题意:取出字符串Str里的两个串S,T,问对应位置的的字符在否有一一映射关系。

hash:对于每个字符s=‘a’-‘z’,我们任意找一个i,满足Si==s,(代码里用lower_bound在区间找到最小的位置i)其对应的字符为Ti==t。然后我们判断这段区间里s的hash值是否等于t的hash值。不难证明26个字母都满足时对应hash相同时,才有一一映射关系。(但是不明白我的自然溢出的hash版本为什么错了,但是mod(1e9+7)的版本对了?

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const int maxn=200010;
const int seed=131;
const int Mod=1e9+7;
ll Hash[26][maxn],g[maxn];
int a[26][maxn],N;
char c[maxn];
ll gethash(int chr,int x,int Len)
{
    return ((Hash[chr][x+Len-1]-Hash[chr][x-1]*g[Len]%Mod)+Mod)%Mod;
}
bool check(int x,int y,int Len)
{
    int i,pos;
    for(i=0;i<26;i++){
        pos=lower_bound(a[i]+1,a[i]+1+a[i][0],x)-a[i];
        if(pos>a[i][0]||a[i][pos]>x+Len-1) continue;
        if(gethash(i,x,Len)!=gethash(c[y-x+a[i][pos]]-'a',y,Len))  return false;
    }
    return true;
}
int main()
{
    int Q,x,y,len,i,j;
    scanf("%d%d",&N,&Q);
    scanf("%s",c+1); g[0]=1;
    for(i=1;i<=N;i++){
        g[i]=g[i-1]*seed%Mod;
        for(j=0;j<26;j++) 
           Hash[j][i]=(Hash[j][i-1]*seed+(c[i]-'a'==j))%Mod;        
        a[c[i]-'a'][++a[c[i]-'a'][0]]=i;
    }
    while(Q--){
        scanf("%d%d%d",&x,&y,&len);
        if(check(x,y,len)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

下面是自然溢出的has版本

CodeForces985F:Isomorphic Strings (字符串&hash) CodeForces985F:Isomorphic Strings (字符串&hash)

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const int maxn=200010;
const int seed=131;
ll Hash[26][maxn],g[maxn];
int a[26][maxn],N;
char c[maxn];
ll gethash(int chr,int x,int Len)
{
    return Hash[chr][x+Len-1]-Hash[chr][x-1]*g[Len];
}
bool check(int x,int y,int Len)
{
    int i,pos;
    for(i=0;i<26;i++){
        pos=lower_bound(a[i]+1,a[i]+1+a[i][0],x)-a[i];
        if(pos>a[i][0]||a[i][pos]>x+Len-1) continue;
        if(gethash(i,x,Len)!=gethash(c[y-x+a[i][pos]]-'a',y,Len))  return false; 
    }
    return true;
}
int main()
{
    int Q,x,y,len,i,j;
    scanf("%d%d",&N,&Q);
    scanf("%s",c+1); g[0]=1;
    for(i=1;i<=N;i++){
        g[i]=g[i-1]*seed;
        for(j=0;j<26;j++) 
           Hash[j][i]=Hash[j][i-1]*seed+(c[i]-'a'==j);        
        a[c[i]-'a'][++a[c[i]-'a'][0]]=i;
    }
    while(Q--){
        scanf("%d%d%d",&x,&y,&len);
        if(check(x,y,len)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

View Code

点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
5个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Peter20 Peter20
3年前
mysql中like用法
like的通配符有两种%(百分号):代表零个、一个或者多个字符。\(下划线):代表一个数字或者字符。1\.name以"李"开头wherenamelike'李%'2\.name中包含"云",“云”可以在任何位置wherenamelike'%云%'3\.第二个和第三个字符是0的值wheresalarylike'\00%'4\
Wesley13 Wesley13
3年前
Java中HashMap的实现原理
总结:HashMap的实现原理:1.利用key的hashCode重新hash计算出当前对象的元素在数组中的下标2.存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的keyvalue放入链表中3.获取时,直接找到hash值对应
Stella981 Stella981
3年前
Hash冲突和一致性
对于hash算法,有几个问题避无可避的。问题1:hash冲突的问题?1\.背景介绍:在数据量很大的时候,就会出现hash之后的数值,指向相同的位置,也就是所谓的hash冲突。这个取决于hash算法的好坏,以及数据量的大小,hash算法越差,数据量越大,hash冲突的概率就会越大。2\.然而一旦出现了hash冲突,我们该怎么办
Stella981 Stella981
3年前
JavaScript常用函数
1\.字符串长度截取functioncutstr(str,len){vartemp,icount0,patrn/^\x00\xff/,strre"";for(vari
Wesley13 Wesley13
3年前
Mysql 表分区分类
针对Mysql数据库,表分区类型简析。【1】表分区类型(1)Range分区:按范围分区。按列值的范围区间进行分区存储;比如:id小于10存储在一个分区;id大于10小于20存储在另外一个分区;(2)List分区:按离散值集合分区。与range分区类似,不过它是按离散值进行分区。(3)Hash分区:按hash算法结果分区。对用户定义的表达式所返
哈希游戏的特点
我们可以简单认为哈希值就是将“账页信息”进行哈希算法,计算得到一串字符密码,那么哈希算法就是区块链保证交易信息不被篡改的单向密码机制。哈希算法在接收一段明文(也就是账页信息)后,以一种不可逆的方式将其转化为一段长度较短、位数固定的散列数据。Hash函数的特点哈希(Hash)函数具有如下特点。易压缩:对于任意大小的输入x,Hash值的长度很小,在实际应用中,函
Ceph的crush算法与一致性hash对比介绍
一致性hash的基本思想是,有一个hash函数,这个hash函数的值域形成了一个环(收尾相接:thelargesthashvaluewrapsaroundtothesmallesthashvalue),然后存储的节点也通过这个hash函数随机的分配到这个环上,然后某个key具体存储到哪个节点上,是由这个key取hash函数对应到环的一个位置,然后沿着这个位置顺时针找到的第一个节点负责这个key的存储。这样环上的每个节点负责和它前面节点之间的这个区间的数据的存储。