字符串hash以及7大问题(1).ppt

1、1,By peterpan,字符串hash简介 那么，我要求Slr这个子串的hash值 hashl.r=(hashr-hashl-1*(p(r-1+1)%mod（假设字符串下标从1开始） 没啦！用这个方法求Slr的hash值 但注意下取模时候的问题！,取模的问题,hashl.r=(hashr-hashl-1*(p(r-1+1)%mod hashl.r是不是可能有负数？ 怎么办呢？当得到的hashl.r0的时候，hashl.r+=mod，就好啦。 这样就可以保证每个子串的hash值在 0, mod-1的范围内，准确地用hash值来处 理字符串,常用的几个字符串hash法,1. unsigned

2、long long hashN; hashi=hashi-1*p（自动取模） 2. hashi=(hashi-1*p+idx(si)%mod 3. 双hash hash1i=(hash1i-1*p+idx(si)%mod1 hash2i=(hash2i-1*p+idx(si)%mod2 pair表示一个字符串！,hash法 一,unsigned long long hashN; 定义一个unsigned long long类型的变量，它的范围是在0, 264) 内，这就相当于，当数超不过264-1后，它会溢出！这就相当于一个数模264的过程。 那么hash函数可以理解为： hashi=(has

3、hi-1*p)%(264) P取一个大素数，一般习惯取1e9+7或1e9+9 安全指数：三星（所以并不是很安全）,hash取法二,这个之前已经提到过了。 hashi=(hashi-1*p+idx(si)%mod p取一个6到8位的素数，mod取一个大素数，一般取1e9+7或1e9+9 安全指数：四星 （还可以）,hash取法三,double hash 即取两个mod值，mod1和mod2 hash1i=(hash1i-1*p+idx(si)%mod1 hash2i=(hash2i-1*p+idx(si)%mod2 mod1一般取1e9+7，mod2一般取1e9+9为什么这么取？ 1000000

4、007和1000000009是一对孪生素数，取它们，冲突的概率极低！ 安全指数：五星！（非常稳！）,更多的hash取法,可以这么说，hash某种程度上就是乱搞，把hash函数弄的越没有规律越好，使得冲突的概率小到 大部分数据都卡不掉。 如果你开心，你想triple hash，ultra hash， rampage hash 都没有问题！ 但请注意，hash的维度越高，耗时越高，耗内存越大！一般情况下，single hash可以被hack掉，但double hash极难被hack掉， 用double hash足以解决问题,字符串hash题目,下面我们通过7道题目来阐述字符串hash的用法，这7道

5、题目，很多道还需要用到二分搜索，因为字符串上很多性质满足二分的单调性，用二分+hash的办法能够在高效时间内解决许多字符串问题。,字符串hash问题一,问题：给两个字符串S1，S2，求S2是否是 S1的子串，并求S2在S1中出现的次数 数据范围： 1=|S1|，|S2|=10000 （kmp是可以做，但请用hash去思考）,字符串hash问题二,问题：给N个单词串，和一个文章串，求每个单词串是否是文章串的子串，并求每个单词在文章中出现的次数。 数据范围 文章串长度：1,105 N个单词串总长：1,106,字符串hash问题二,解法： 把每一个单词hash成整数，再把文章的每一个子串hash成整

6、数，接下来只需要进行整数上的查找即可。 复杂度：O(|A|2+|S|) 用AC自动机可以做到O(|A|+|S|)的复杂度 |S|是单词串总长，|A|是文章长度,字符串hash问题三,问题：给两个字符串S1,S2，求它们的最长公共子串的长度。 数据范围： 1=|S1|，|S2|=105,字符串hash问题三,解法： 将S1的每一个子串都hash成一个整数 将S2的每一个子串都hash成一个整数 两堆整数，相同的配对，并且找到所表示的字符串长度最大的即可。 复杂度：O(|S1|2+|S2|2) 用后缀数组可以优化到O(|S|*log|S|) 虽然如此，但hash也是一种可行方法,hash二分,下面

7、的问题，都需要用到hash二分搜索的方法去解决。 会发现，字符串上的很多的性质，都能满足二分的单调性，而hash的作用是判断两个字符串是否一致。,字符串hash问题四,问题：给一个字符串S，求S的最长回文子串。 比如abcbbabbc的最长回文子串是cbbabbc，bbabb也是回文串，但不是最长的 数据范围： 1|S|=105 什么是回文串？,字符串hash问题四,解法：先求子串长度位奇数的，再求偶数的。枚举回文子串的中心位置，然后二分子串的长度，直到找到一个该位置的最长回文子串，不断维护长度最大值即可。 复杂度：O(|S|*log|S|) 用manacher可以做到O(|S|)的复杂度,字

8、符串hash问题五,给一个字符串S，求S的每个后缀与S的最长公共前缀（LCP）。 Longest common prefix 数据范围: 1=|S|=100000,字符串hash问题五,解法：枚举每一个后缀的起始位置，二分长度，求出每个后缀与S的最长公共前缀。 复杂度：O(|S|*log|S|) 用extend-kmp可以做到O(|S|)的复杂度,字符串hash问题六,给一个字符串S，求S的最小表示法。 对一个字符串，进行如下两种操作： 1. 把头字符放到尾 2. 把尾字符放到头 不断进行上述2个操作，直到S的字典序达到最小，此时的S是原串的最小表示法 比如bbabc，最小表示法是abcbb,字符串hash问题六,解法：不断取两个起始位置，用二分hash的方法判断他们的字典序，直到找到字典序最小的表示法。 复杂度：O(|S|*log|S|) 用贪心方法可以做到O(|S|),字符串hash问题七,给一个字符串S，求S的最长连续重复子串。 数据范围： 1=|S|=105 比如 abcabababc 的最长连续重复