【NOIP2017提高A组冲刺11.8】好文章

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

typedef long long ll;

struct HH{

    ll mod,base,d;

    ll sta;

    void update(int x){

        sta+=x;sta*=base;sta%=mod;

    }

    void del(int x){

        sta-=(x*d);

        while(sta<) sta+=mod;

    }

}h1,h2;

const int MAXN=;

ll qpow(ll x,int y,ll mod){

    ll ret=;

    while(y){

        if(y&){ret*=x;ret%=mod;}

        x*=x;x%=mod;

        y>>=;

    }

    return ret;

}

struct Node{

    ll x,y;

    Node(ll u=,ll v=){x=u;y=v;}

    bool operator <(const Node &rhs) const {

        return x==rhs.x?y<rhs.y:x<rhs.x;

    }

}node[MAXN];

int tot;

int n,m;

char s[MAXN];

int ans=;

signed main(){

//    freopen("article.in","r",stdin);

//    freopen("article.out","w",stdout);

    scanf("%d%d",&n,&m);

    h1.base=;h2.base=;

    h1.mod=;

    h2.mod=;

    h1.d=qpow(h1.base,m,h1.mod);

    h2.d=qpow(h2.base,m,h2.mod);

    scanf("%s",s+);

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

        h1.update(s[i]-'a');

        h2.update(s[i]-'a');

    }

    node[++tot]=(Node(h1.sta,h2.sta));

    for(int i=m+;i<=n;i++){

        h1.del(s[i-m]-'a');

        h2.del(s[i-m]-'a');

        h1.update(s[i]-'a');

        h2.update(s[i]-'a');

        node[++tot]=(Node(h1.sta,h2.sta));

    }

    sort(node+,node++tot);

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

        if(node[i].x!=node[i-].x||node[i].y!=node[i-].y) ans++;

    }

    cout<<ans;

    return ;

}