好文章

LELElele01 · 2020-08-05 20:12:30 · 个人记录

好文章

本题部分分很好拿，用map加string的操作就可以完成

发现瓶颈在与不能O(1)求出区间字符的值

然后发现hash可以满足要求，最多1个log就可求出字符的值

但一个hash可能会被卡掉，所以我们用两个hash hash

hash[i]=hash[i-1]*p+str[i]%P
hash(l,r)=hash[r]-hash[l-1]^(r-l+1)

这是经典的hash

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=2e5+5;
int n,m;
char s[N];
int hash11[N],hash22[N];
ll p1=29,p2=31,P1=1000000007,P2=1000000009;
ll ksm1(ll x,ll pow){
    ll ans=1,res=x;
    while(pow){
        if(pow&1) ans=ans*res%P1;
        res=res*res%P1;
        pow>>=1;
    }
    return ans;
}
ll ksm2(ll x,ll pow){
    ll ans=1,res=x;
    while(pow){
        if(pow&1) ans=ans*res%P2;
        res=res*res%P2;
        pow>>=1;
    }
    return ans;
}
ll hash1(int l,int r){
    return ((hash11[r]-(1ll*(hash11[l-1])*ksm1(p1,(r-l+1)))%P1)%P1+P1)%P1;
}
ll hash2(int l,int r){
    return ((hash22[r]-(1ll*(hash22[l-1]*ksm2(p2,(r-l+1))))%P2)%P2+P2)%P2;
}
struct node{
    int x,y;
}q[N];
bool cmp(node a,node b){
    return a.x<b.x;
}
int main(){
    scanf("%d%d",&n,&m);
    scanf("%s",(s+1));
    for(int i=1;i<=n;i++){
        int now=s[i]-'a';
        hash11[i]=(1ll*hash11[i-1]*p1+1ll*now)%P1;
        hash22[i]=(1ll*hash22[i-1]*p2+1ll*now)%P2;
    }
    int s=0;
    for(int l=1;l+m-1<=n;l++){
        int r=l+m-1;s++;
        ll tp1=hash1(l,r),tp2=(hash2(l,r));
        q[s].x=tp1;
        q[s].y=tp2;
    }
    sort(q+1,q+s+1,cmp);
    int cnt=1;
    for(int i=2;i<=s;i++){
        if((q[i].x!=q[i-1].x)||(q[i].y!=q[i-1].y)){
            cnt++;
        }
    }
    printf("%d",cnt);
}