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

1,By peterpan,字符串hash简介 & 有关字符串hash的 7个问题！,字符串hash,关于字符串hash，就一句话： 把字符串有效地转化为一个整数 在计算机里，用的是二进制编码。在很多语言里，都是用数字作为数组的下标。因为用数字来存储、表达一个object非常方便。 如果能有一种算法，把每个字符串有效地、”唯一”的映射到每个“不同”的整数，我们就能很好的处理字符串。,hash函数,现在我们希望找到一个hash函数，使得每一个字符串都能够映射到一个整数上 比如hashi=(hashi-1*p+idx(si)%mod 字符串：abc，bbc，aba，aadaabac 字符串下标从0开始 先把a映射为1，b映射为2，c-3，d-4,即idx(a)=1, idx(b)=2, idx(c)=3,idx(d)=4； 好！开始对字符串进行hash,hash函数,假设我们取p=13 ，mod=101 先把abc映射为一个整数 hash0=1，表示 a 映射为1 hash1=(hash0*p+idx(b)%mod=15，表示 ab 映射为 15 hash2=(hash1*p+idx(c)%mod=97 这样，我们就把 abc 映射为 97 这个数字了。,hash函数,用同样的方法，我们可以把bbc，aba，aadaabac都映射到一个整数 用同样的hash函数，得到如下结果 abc - 97 bbc - 64 aba - 95 aadaabac - 35 那么，我们发现，这是一个字符串到整数的映射,hash函数,这样子，我们就可以记录下每个字符串对应的整数，当下一次出现了一个已经出现的字符串时，查询整数是否出现过，就可以知道 字符串是否重复出现。 现在要判断两个字符串是否一致，怎么办呢？直接用它们的hash值判断即可，若hash值一致，则认为字符串一致； 若hash值不一致，则认为是不同的字符串。,hash,我们要判断两个字符串是否一致，没有那么麻烦，直接先判断长度是否一致，然后再判断每个对应的字符是否一致即可。 但，如果要判断多个字符串里有多少个不同的字符串，怎么办呢？ 两两字符串都进行比较？时间复杂度太高 把每个字符串hash成一个整数，然后把所有整数进行一个去重操作，即可知道答案了。 我们来具体看下这个问题。,关于hash的简单问题,问题： 给N个字符串，每个字符串长度不超过100，问这些字符串里有多少个不同的字符串？ 即相同字符串只取一个，最后剩下多少字符串？ 数据范围：1=N=100000 字符集：小写英文字母（a-z）,输入和输出,Input 第一行输入一个整数N 接下来N行输入N个字符串，每个字符串长度不超过100 Output 输出一个整数，表示有多少个不同的串。,样例,Sample Input 7 aaaaa aba bba aba abcde bba,Sample Output 4 解释：很显然，左边字符串集去重后只剩4个字串 aaaaa，aba bba，abcde,解题方法：hash,用hash来做. 我们把每个字符串hash为一个整数，这样每个整数都表示成一个字符串 把N个字符串存下来，排个序，去重，剩下多少个整数，就表示去重后有多少个字符串 当然，也可以用字典树来解。但字典树耗内存会比hash大得多,hash算法的问题！,我们想，刚才给出的hash函数 hashi=(hashi-1*p+idx(si)%mod 并且我们取的是p=13，mod=101； 这样做真的不会有问题吗？ 实际上是会有的，问题就是 冲突！ 有没有可能两个不同的字符串，映射到了一个整数上，这样子就会导致结果出错？ 可能！怎么解决呢？,字符串hash,解决的方法非常简单，想办法调整p和mod，使得冲突概率减小之又小。 那么怎么调整才能使冲突概率小之又小呢？ 一句话告诉你，p取一个较大素数，mod取一个大素数。 习惯上，p取一个6到8位的素数即可，mod一般取大素数 1e9+7（1000000007）或 1e9+9（1000000009） 可是，为什么这样做就会冲突概率小之又小？,hash的解释,我们想，如果mod取的很小，mod=97，或者更小，mod=13，它与mod取一个大数相比，比如1e9+7=1000000007，是不是冲突的概率就会更大？ 同时考虑p，p取2，相比p取一个较大的素数，是不是冲突的概率会更大？ 换句话说，我们希望取得一个p和mod，使得这个函数”越乱越好”，“越没有规律越好”，这样才能降低冲突的概率！,p和mod的取法,我们一般认为p和mod一般取素数，p取一个较大的素数即可（6位到8位），mod取一个大素数，比如1e9+7，或者1e9+9。 具体为什么这样做就能够大概率地避免冲突，或者它具体的概率是多少，若想钻研，请google 但，可以肯定的是，这样子的取法，冲突的概率非常低！低到我们可以基本放心地去用这个函数解决一般的hash问题。,如何求一个子串的hash值？,实在抱歉，算法讲座的时候，忘记了这部分，现在补上。 在之前，我们求出了hashi，表示第i个前缀的hash值。现在怎么求出每个子串的 hash值呢？ 我们看下hash的公式： hashi=(hashi-1*p+idx(si)%mod 这表示第 i 个前缀的hash值，是一个hash的前缀和。,如何求一个子串的hash值？,hashi=(hashi-1*p+idx(si)%p; 那么，我要求Slr这个子串的hash值 hashlr=(hashr-hashl-1*(p(r-1+1)%mod（假设字符串下标从1开始） 没啦！用这个方法求Slr的hash值 但注意下取模时候的问题！,取模的问题,hashlr=(hashr-hashl-1*(p(r-1+1)%mod hashlr是不是可能有负数？ 怎么办呢？当得到的hashlr0的时候，hashlr+=mod，就好啦。 这样就可以保证每个子串的hash值在 0, mod-1的范围内，准确地用hash值来处 理字符串,常用的几个字符串hash法,1. unsigned 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=(hashi-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为什么这么取？ 1000000007和1000000009是一对孪生素数，取它们，冲突的概率极低！ 安全指数：五星！（非常稳！）,更多的hash取法,可以这么说，hash某种程度上就是乱搞，把hash函数弄的越没有规律越好，使得冲突的概率小到 大部分数据都卡不掉。 如果你开心，你想triple hash，ultra hash， rampage hash 都没有问题！ 但请注意，hash的维度越高，耗时越高，耗内存越大！一般情况下，single hash可以被hack掉，但double hash极难被hack掉， 用double hash足以解决问题,字符串hash题目,下面我们通过7道题目来阐述字符串hash的用法，这7道题目，很多道还需要用到二分搜索，因为字符串上很多性质满足二分的单调性，用二分+hash的办法能够在高效时间内解决许多字符串问题。,字符串hash问题一,问题：给两个字符串S1，S2，求S2是否是 S1的子串，并求S2在S1中出现的次数 数据范围： 1=|S1|，|S2|=10000 （kmp是可以做，但请用hash去思考）,字符串hash问题二,问题：给N个单词串，和一个文章串，求每个单词串是否是文章串的子串，并求每个单词在文章中出现的次数。 数据范围 文章串长度：1,105 N个单词串总长：1,106,字符串hash问题二,解法： 把每一个单词hash成整数，再把文章的每一个子串hash成整数，接下来只需要进行整数上的查找即可。 复杂度：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二分,下面的问题，都需要用到hash二分搜索的方法去解决。 会发现，字符串上的很多的性质，都能满足二分的单调性，而hash的作用是判断两个字符串是否一致。,字符串hash问题四,问题：给一个字符串S，求S的最长回文子串。 比如abcbbabbc的最长回文子串是cbbabbc，bbabb也是回文串，但不是最长的 数据范围： 1|S|=105 什么是回文串？,字符串hash问题四,解法：先求子串长度位奇数的，再求偶数的。枚举回文子串的中心位置，然后二分子串的长度，直到找到一个该位置的最长回文子串，不断维护长度最大值即可。 复杂度：O(|S|*log|S|) 用manacher可以做到O(|S|)的复杂度,字符串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的方法判断他们的字典序，直到找到字典