CodeForces985F：Isomorphic Strings （字符串&hash）

题意：取出字符串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=;

const int seed=;

const int Mod=1e9+;

ll Hash[][maxn],g[maxn];

int a[][maxn],N;

char c[maxn];

ll gethash(int chr,int x,int Len)

{

    return ((Hash[chr][x+Len-]-Hash[chr][x-]*g[Len]%Mod)+Mod)%Mod;

}

bool check(int x,int y,int Len)

{

    int i,pos;

    for(i=;i<;i++){

        pos=lower_bound(a[i]+,a[i]++a[i][],x)-a[i];

        if(pos>a[i][]||a[i][pos]>x+Len-) 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+); g[]=;

    for(i=;i<=N;i++){

        g[i]=g[i-]*seed%Mod;

        for(j=;j<;j++)

           Hash[j][i]=(Hash[j][i-]*seed+(c[i]-'a'==j))%Mod;

        a[c[i]-'a'][++a[c[i]-'a'][]]=i;

    }

    while(Q--){

        scanf("%d%d%d",&x,&y,&len);

        if(check(x,y,len)) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

下面是自然溢出的has版本

#include<bits/stdc++.h>

using namespace std;

#define ll unsigned long long

const int maxn=;

const int seed=;

ll Hash[][maxn],g[maxn];

int a[][maxn],N;

char c[maxn];

ll gethash(int chr,int x,int Len)

{

    return Hash[chr][x+Len-]-Hash[chr][x-]*g[Len];

}

bool check(int x,int y,int Len)

{

    int i,pos;

    for(i=;i<;i++){

        pos=lower_bound(a[i]+,a[i]++a[i][],x)-a[i];

        if(pos>a[i][]||a[i][pos]>x+Len-) 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+); g[]=;

    for(i=;i<=N;i++){

        g[i]=g[i-]*seed;

        for(j=;j<;j++)

           Hash[j][i]=Hash[j][i-]*seed+(c[i]-'a'==j);

        a[c[i]-'a'][++a[c[i]-'a'][]]=i;

    }

    while(Q--){

        scanf("%d%d%d",&x,&y,&len);

        if(check(x,y,len)) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

巴特西

CodeForces985F：Isomorphic Strings （字符串&hash）

最新文章

热门文章