哈希与字典树与KMP

时间：2021-12-26 17:39:30

　　hash讲解

　　主要记录hash的公式：

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

        Hash[i]=(Hash[i-]*base%mod+(s[i]-'A'+)%mod)%mod;

    }

　　求hash的公式是这个，怎么求一小段的hash值呢？

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

        p[i]=p[i-]*base%mod;

    }

ll get(int l, int r) {
　　return (Hash[r]%mod-Hash[l-1]*p[r-l+1]%mod)%mod;
}

　　我一直不理解为什么要乘p[r-l+1]呢？现在明白啦*★,°*:.☆(￣▽￣)/$:*.°★* 。

　　首先给你一个字符串abcdef，hash[6]=a*p^5+b*p^4+c*p^3+d*p^2+e*p^1+f*p^0。如果我们要求def的hash值怎么求呢？

　　我们知道hash[6]=a*p^5+b*p^4+c*p^3+d*p^2+e*p^1+f*p^0，hash[3]=a*p^2+b*p^1+c*p^0。

　　而def的hash值是d*p^2+e*p^1+f*p^0，那么就看得出def的hash值是(Hash[r]%mod-Hash[l-1]*p[r-l+1]%mod)%mod这个公式。

　　板子：

/*  gyt

       Live up to every day            */

#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<cstring>

#include<queue>

#include<set>

#include<string>

#include<map>

#include <time.h>

#define PI acos(-1)

using namespace std;

typedef long long ll;

typedef double db;

const int maxn = 4e4+;

const ll maxm = 1e7;

const int mod = 1e9+;

const int INF = <<;

const db eps = 1e-;

const ll base = 1e9+;

ll Hash[maxn];

ll p[maxn];

char s1[maxn], s2[maxn];

void init(char *s) {

    p[]=;

    Hash[]=;

    int len=strlen(s+);

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

        p[i]=p[i-]*base%mod;

    }

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

        Hash[i]=(Hash[i-]*base%mod+(s[i]-'A'+)%mod)%mod;

    }

}

ll get(int l, int r) {

    return (Hash[r]%mod-Hash[l-]*p[r-l+]%mod)%mod;

}

void solve() {

    while(scanf("%s", s2+)!=EOF) {

        if (s2[]=='#')  break;

        scanf("%s", s1);

        int len1=strlen(s1);

        int len2=strlen(s2+);

        int num=, biao=;

        init(s2);

        ll haha=;

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

            haha = (haha*base%mod+(s1[i]-'A'+)%mod)%mod;

        }

        int ans=;

        for (int i=; i+len1-<=len2; i+=len1) {

            ll ha=get(i, i+len1-);

            if (ha==haha)  ans++;

        }

        printf("%d\n", ans);

    }

}

int main() {

    int t = ;

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

    //scanf("%d", &t);

    while(t--)

        solve();

    return ;

}

　　字典树板子

　　

/*  gyt

       Live up to every day            */

#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<cstring>

#include<queue>

#include<set>

#include<string>

#include<map>

#include <time.h>

#define PI acos(-1)

using namespace std;

typedef long long ll;

typedef double db;

const int maxn = 4e4+;

const ll maxm = 1e7;

const int modd = ;

const int INF = <<;

const db eps = 1e-;

struct Trie{

    int v;

    Trie *next[];

};

Trie root;

void creat(char *str) {

    int len=strlen(str);

    Trie *p=&root, *q;

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

        int id=str[i]-'a';

        if (p->next[id]==NULL) {

            q=(Trie *)malloc(sizeof(root));

            q->v=;

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

                q->next[j]=NULL;

            p->next[id]=q;

            p=p->next[id];

        }

        else {

            p->next[id]->v++;

            p=p->next[id];

        }

    }

}

int Find(char *str) {

    int len=strlen(str);

    Trie *p=&root;

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

        int id=str[i]-'a';

        p=p->next[id];

        if (p==NULL)  return ;

    }

    return p->v;

}

void solve() {

    char str[];

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

        root.next[i]=NULL;

    while(gets(str)) {

        if (str[]=='\0')  break;

        creat(str);

    }

    while(gets(str)) {

        if (str[]=='\0')  break;

        int ans=Find(str);

        printf("%d\n", ans);

    }

}

int main() {

    int t = ;

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

    scanf("%d", &t);

    while(t--)

        solve();

    return ;

}

相关文章