不懂hash是什么的盆友给出直通车:滴滴滴,开车啦~

如果你看懂了的话:

hash模板来也~

#include <cstdio>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + ;  //

const int D = ;      //质数

const int MD = 1e9 + ; //大质数 

int n;

string s;

unsigned long long f[N], g[N]; //g[i]为D的i次方 

void prehash(int n) //进行预处理

{

// 预处理时,注意到数字可能很大,对一个数 MD 取模

    f[] = s[];//预处理前缀和(进行强制类型转)

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

        f[i] = (1LL * f[i-] * D + s[i-]) % MD;

    g[] = ; //预处理D

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

        g[i] = 1LL * g[i-] * D % MD;

}

int hash(int l, int r) //计算区间 [l,r] 的哈希值

{

    int a = f[r];

    int b = 1LL * f[l-] * g[r-l+] % MD;

    return (a - b + MD) % MD; //+MD是为了防止出现负数

}

int main()

{

    cin >> s;

    n = s.length();

    prehash(n);

    while(!cin.eof())//直至按ctrl+z键退出!

    {

        int l, r;

        cin >> l >> r;

        cout << s.substr(l-, r-l+) << ": " << hash(l, r) << endl;

        //从l-1到r-l+1的字符

    }

    return ;

}

良心推荐洛谷练手题:

1.P3370【模板】字符串哈希

题目描述

如题，给定N个字符串（第i个字符串长度为Mi，字符串内包含数字、大小写字母，大小写敏感），请求出N个字符串中共有多少个不同的字符串。

友情提醒：如果真的想好好练习哈希的话，请自觉，否则请右转PJ试炼场:)

输入输出格式

输入格式：

第一行包含一个整数N，为字符串的个数。

接下来N行每行包含一个字符串，为所提供的字符串。

输出格式：

输出包含一行，包含一个整数，为不同的字符串个数。

输入输出样例

输入样例#1：

5

abc

aaaa

abc

abcc

12345

输出样例#1：

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=10，Mi≈6，Mmax<=15;

对于70%的数据：N<=1000，Mi≈100，Mmax<=150

对于100%的数据：N<=10000，Mi≈1000，Mmax<=1500

样例说明：

样例中第一个字符串(abc)和第三个字符串(abc)是一样的，所以所提供字符串的集合为{aaaa,abc,abcc,12345}，故共计4个不同的字符串。

Tip：感兴趣的话，你们可以先看一看以下三题：

BZOJ3097：http://www.lydsy.com/JudgeOnline/problem.php?id=3097

BZOJ3098：http://www.lydsy.com/JudgeOnline/problem.php?id=3098

BZOJ3099：http://www.lydsy.com/JudgeOnline/problem.php?id=3099

如果你仔细研究过了（或者至少仔细看过AC人数的话），我想你一定会明白字符串哈希的正确姿势的^_^

思路:

　　题解里面是有很多种方法的,但是我认为能够搞懂一种就已经很不错了……

　　所以我给出的思路就是用set来进行统计,set只能够允许一种数字出现一次,所以我们就可以将给出的字符串的hash值求出来

　　然后加入到set里面,最后直接输出set里面有多少数就行啦~

PS:

　　　　　　定义函数的时候不要用"hash"这个名字,在洛谷里是关键字!!!

上代码=u=:

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string>

#include <cstring>

#include <set>

using namespace std;

typedef unsigned long long ull;

typedef long long LL;

set<ull>ssr;

const int N = ;

const int D = ;     //质数

const ull MD= 1e9 + ; //大质数 

LL n,len;

string s;

ull f[N];//预处理前缀和

ull g[N];//预处理 D的i次方 

int yuchuli(int q)

{

    memset(f,,sizeof(f));

    memset(g,,sizeof(g));

    f[]=s[];

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

        f[i] = (1LL * f[i-] * D +s[i-]) % MD;

    g[]=;

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

        g[i] = 1LL * g[i-] * D % MD;

}

int hashs(int l,int r)

{

    ull a = f[r];

    ull b = 1LL * f[l-] *g[r-l+] % MD;

    return (a - b + MD) % MD;

}

int main()

{

    cin>>n;

    while(n--)

    {

        cin>>s;

        len=s.length();

        yuchuli(len);

        ull qq = hashs(,len);

        ssr.insert(qq);

    }

    cout<<ssr.size();

    return ;

}

2.

cogs249. [POI2000] 最长公共子串

★★★ 输入文件：pow.in 输出文件：pow.out 简单对比
时间限制：1 s 内存限制：256 MB

给出几个由小写字母构成的单词，求它们最长的公共子串的长度。

任务

从文件中读入单词
计算最长公共子串的长度
输出结果到文件

输入

文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。

输出：

仅一行，一个整数，最长公共子串的长度。

样例输入：

3

abcb

bca

acbc

样例输出：

思路:

　　正解据说是后缀数组呢！后缀数组是什么鬼???我又不会...只好胡乱搞hash啦~结果一搞...奇迹的就WA了一个点,结果又胡乱改了一下Mod,然后就A了...真不可思议w

　　　　Ps:脑洞产物(正解xxx),能不能过全看 your rp!!!

　　话不多说:

　　hash的思路:

　　　　　　pre:

　　　　　　　　　　首先话不多说，跟普通hash一样把每一个单词的hash值求一下，然后快乐地开始进行二分公共子串的长度

　　　　　　　　　　然后我们又设置了vis和times两个数组，其中times[i]表示当前hash值i已经出现在几个单词里面。

　　　　　　　　　　接着枚举每个单词中子串的开始位置，用O(1)时间求该子串的hash，然后times加一。

　　　　　　　　　　（当然同一个长单词里面可能有相同的子串，所以用vis记录一下这个hash值最后出现在第几个单词中，来判断该子串在当前字符串中是不是第一次出现。）

　　　　　　结束条件:

　　　　　　　　　　如果times加到n了，说明每个单词里面都有这个子串，这个解是正确的，然后顺路更新一下ans的值！

　　　　　　时间复杂度:

　　　　　　　　　　1）求hash是O(|S|*n)，|S|表示最长的子串长度。

　　　　　　　　　　2）二分答案部分为(log|S|*n*|S|)。

　　　　　　　　故总体的期望复杂度为O(log|S|*|S|*n)，而n只有5，|S|只有2000，显然轻松过去..

　　　　　　　　over!!!

坑点:

　　在选取Mod以及D的时候，一定要多用几组，防止发生冲突。

上代码=v=:

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#define INF 0x7fffffff

#define LL long long

using namespace std;

const int D = ;

const int Mod = ;

const int N = ;

const int le = ;

int n,minl,ans;

LL f[N][le],g[le];

int len[N];

char str[le];

int vis[Mod+],times[Mod+];

bool check(int x)

{

    memset(vis,,sizeof(vis));

    memset(times,,sizeof(times));

    LL cv=g[x];

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

    {

        for(int j=x;j<=len[i];++j)

        {

            LL nowhash=(f[i][j]-(f[i][j-x]*cv)%Mod+Mod)%Mod;

            if(vis[nowhash]!=i)

            {

                ++times[nowhash];

                vis[nowhash]=i;

                if(times[nowhash]==n)

                    return true;

            }

        }

    }

    return false;

}

void prehash(int i)

{

    f[i][]=str[]-'a'+;

    for(int j=;j<=len[i];++j)

        f[i][j]=(f[i][j-]*D+(str[j-]-'a'+))%Mod;

}

void dichotomy()

{

    int l=,r=minl+;

    while(l<r)

    {

        int mid=(l+r)>>;

        if(check(mid))

            ans=mid,l=mid+;

        else

            r=mid;

    }

    printf("%d",ans);

}

int main()

{

    freopen("pow.in", "r", stdin);

    freopen("pow.out", "w", stdout);

    scanf("%d",&n);

    minl=INF;

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

    {

        scanf("%s",str);

        len[i]=strlen(str);

        if(len[i]<minl) minl=len[i];

        prehash(i);

    }

    g[]=;

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

        g[i]=1LL*g[i-]*D%Mod;

    dichotomy();

    return ;

}

巴特西

【テンプレート】字符串hash