《字符串hash以及7大问题》由会员分享，可在线阅读，更多相关《字符串hash以及7大问题（39页珍藏版）》请在金锄头文库上搜索。
1、1By peterpanBy peterpan 字符串字符串hashhash简介简介 & & 有关字符串有关字符串hashhash的的 7 7个问题！个问题！2字符串hash关于字符串hash，就一句话：把字符串有效地转化为一个整数在计算机里，用的是二进制编码。在很多语言里，都是用数字作为数组的下标。因为用数字来存储、表达一个object非常方便。如果能有一种算法，把每个字符串有效地、”唯一”的映射到每个“不同”的整数，我们就能很好的处理字符串。3hash函数现在我们希望找到一个hash函数，使得每一个字符串都能够映射到一个整数上比如hashi=(hashi-1*p+idx(si)%mod字符
2、串：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；好！开始对字符串进行hash4hash函数假设我们取p=13，mod=101先把abc映射为一个整数hash0=1，表示a映射为1hash1=(hash0*p+idx(b)%mod=15，表示ab映射为15hash2=(hash1*p+idx(c)%mod=97这样，我们就把abc映射为97这个数字了。5hash函数用同样的方法，我们可以把bbc，aba，aadaabac都映射到一个整数用同样的hash函数，得到如下
3、结果abc-97bbc-64aba-95aadaabac-35那么，我们发现，这是一个字符串到整数的映射6hash函数这样子，我们就可以记录下每个字符串对应的整数，当下一次出现了一个已经出现的字符串时，查询整数是否出现过，就可以知道字符串是否重复出现。现在要判断两个字符串是否一致，怎么办呢？直接用它们的hash值判断即可，若hash值一致，则认为字符串一致；若hash值不一致，则认为是不同的字符串。7hash我们要判断两个字符串是否一致，没有那么麻烦，直接先判断长度是否一致，然后再判断每个对应的字符是否一致即可。但，如果要判断多个字符串里有多少个不同的字符串，怎么办呢？两两字符串都进行比较？时
4、间复杂度太高把每个字符串hash成一个整数，然后把所有整数进行一个去重操作，即可知道答案了。我们来具体看下这个问题。8关于hash的简单问题问题：给N个字符串，每个字符串长度不超过100，问这些字符串里有多少个不同的字符串？即相同字符串只取一个，最后剩下多少字符串？数据范围：1=N=100000字符集：小写英文字母（a-z）9输入和输出Input第一行输入一个整数N接下来N行输入N个字符串，每个字符串长度不超过100Output输出一个整数，表示有多少个不同的串。10样例SampleInput7aaaaaababbaabaabcdebbaSampleOutput4解释：很显然，左边字符串集去重
5、后只剩4个字串aaaaa，ababba，abcde11解题方法：hash用hash来做.我们把每个字符串hash为一个整数，这样每个整数都表示成一个字符串把N个字符串存下来，排个序，去重，剩下多少个整数，就表示去重后有多少个字符串当然，也可以用字典树来解。但字典树耗内存会比hash大得多12hash算法的问题！我们想，刚才给出的hash函数hashi=(hashi-1*p+idx(si)%mod并且我们取的是p=13，mod=101；这样做真的不会有问题吗？实际上是会有的，问题就是冲突！有没有可能两个不同的字符串，映射到了一个整数上，这样子就会导致结果出错？可能！怎么解决呢？13字符串hash
6、解决的方法非常简单，想办法调整p和mod，使得冲突概率减小之又小。那么怎么调整才能使冲突概率小之又小呢？一句话告诉你，p取一个较大素数，mod取一个大素数。习惯上，p取一个6到8位的素数即可，mod一般取大素数1e9+7（1000000007）或1e9+9（1000000009）可是，为什么这样做就会冲突概率小之又小？14hash的解释我们想，如果mod取的很小，mod=97，或者更小，mod=13，它与mod取一个大数相比，比如1e9+7=1000000007，是不是冲突的概率就会更大？同时考虑p，p取2，相比p取一个较大的素数，是不是冲突的概率会更大？换句话说，我们希望取得一个p和mod，
7、使得这个函数”越乱越好”，“越没有规律越好”，这样才能降低冲突的概率！15p和mod的取法我们一般认为p和mod一般取素数，p取一个较大的素数即可（6位到8位），mod取一个大素数，比如1e9+7，或者1e9+9。具体为什么这样做就能够大概率地避免冲突，或者它具体的概率是多少，若想钻研，请google但，可以肯定的是，这样子的取法，冲突的概率非常低！低到我们可以基本放心地去用这个函数解决一般的hash问题。16如何求一个子串的hash值？实在抱歉，算法讲座的时候，忘记了这部分，现在补上。在之前，我们求出了hashi，表示第i个前缀的hash值。现在怎么求出每个子串的hash值呢？我们看下has
8、h的公式：hashi=(hashi-1*p+idx(si)%mod这表示第i个前缀的hash值，是一个hash的前缀和。17如何求一个子串的hash值？hashi=(hashi-1*p+idx(si)%p;那么，我要求Slr这个子串的hash值hashl.r=(hashr-hashl-1*(p(r-1+1)%mod（假设字符串下标从1开始）没啦！用这个方法求Slr的hash值但注意下取模时候的问题！18取模的问题hashl.r=(hashr-hashl-1*(p(r-1+1)%modhashl.r是不是可能有负数？怎么办呢？当得到的hashl.r0的时候，hashl.r+=mod，就好啦。这样
9、就可以保证每个子串的hash值在0,mod-1的范围内，准确地用hash值来处理字符串19常用的几个字符串hash法1.unsignedlonglonghashN;hashi=hashi-1*p（自动取模）2.hashi=(hashi-1*p+idx(si)%mod3.双hashhash1i=(hash1i-1*p+idx(si)%mod1hash2i=(hash2i-1*p+idx(si)%mod2pair表示一个字符串！20hash法一unsignedlonglonghashN;定义一个unsignedlonglong类型的变量，它的范围是在0,264)内，这就相当于，当数超不过264-1
10、后，它会溢出！这就相当于一个数模264的过程。那么hash函数可以理解为：hashi=(hashi-1*p)%(264)P取一个大素数，一般习惯取1e9+7或1e9+9安全指数：三星（所以并不是很安全）21hash取法二这个之前已经提到过了。hashi=(hashi-1*p+idx(si)%modp取一个6到8位的素数，mod取一个大素数，一般取1e9+7或1e9+9安全指数：四星（还可以）22hash取法三doublehash即取两个mod值，mod1和mod2hash1i=(hash1i-1*p+idx(si)%mod1hash2i=(hash2i-1*p+idx(si)%mod2mod1
11、一般取1e9+7，mod2一般取1e9+9为什么这么取？1000000007和1000000009是一对孪生素数，取它们，冲突的概率极低！安全指数：五星！（非常稳！）23更多的hash取法可以这么说，hash某种程度上就是乱搞，把hash函数弄的越没有规律越好，使得冲突的概率小到大部分数据都卡不掉。如果你开心，你想triplehash，ultrahash，rampagehash都没有问题！但请注意，hash的维度越高，耗时越高，耗内存越大！一般情况下，singlehash可以被hack掉，但doublehash极难被hack掉，用doublehash足以解决问题24字符串hash题目下面我们通
12、过7道题目来阐述字符串hash的用法，这7道题目，很多道还需要用到二分搜索，因为字符串上很多性质满足二分的单调性，用二分+hash的办法能够在高效时间内解决许多字符串问题。25字符串hash问题一问题：给两个字符串S1，S2，求S2是否是S1的子串，并求S2在S1中出现的次数数据范围：1=|S1|，|S2|=10000（kmp是可以做，但请用hash去思考）26字符串hash问题二问题：给N个单词串，和一个文章串，求每个单词串是否是文章串的子串，并求每个单词在文章中出现的次数。数据范围文章串长度：1,105N个单词串总长：1,10627字符串hash问题二解法：把每一个单词hash成整数，再把
13、文章的每一个子串hash成整数，接下来只需要进行整数上的查找即可。复杂度：O(|A|2+|S|)用AC自动机可以做到O(|A|+|S|)的复杂度|S|是单词串总长，|A|是文章长度28字符串hash问题三问题：给两个字符串S1,S2，求它们的最长公共子串的长度。数据范围：1=|S1|，|S2|=10529字符串hash问题三解法：将S1的每一个子串都hash成一个整数将S2的每一个子串都hash成一个整数两堆整数，相同的配对，并且找到所表示的字符串长度最大的即可。复杂度：O(|S1|2+|S2|2)用后缀数组可以优化到O(|S|*log|S|)虽然如此，但hash也是一种可行方法30hash二
14、分下面的问题，都需要用到hash二分搜索的方法去解决。会发现，字符串上的很多的性质，都能满足二分的单调性，而hash的作用是判断两个字符串是否一致。31字符串hash问题四问题：给一个字符串S，求S的最长回文子串。比如abcbbabbc的最长回文子串是cbbabbc，bbabb也是回文串，但不是最长的数据范围：1|S|=105什么是回文串？32字符串hash问题四解法：先求子串长度位奇数的，再求偶数的。枚举回文子串的中心位置，然后二分子串的长度，直到找到一个该位置的最长回文子串，不断维护长度最大值即可。复杂度：O(|S|*log|S|)用manacher可以做到O(|S|)的复杂度33字符串h
15、ash问题五给一个字符串S，求S的每个后缀与S的最长公共前缀（LCP）。Longestcommonprefix数据范围:1=|S|=10000034字符串hash问题五解法：枚举每一个后缀的起始位置，二分长度，求出每个后缀与S的最长公共前缀。复杂度：O(|S|*log|S|)用extend-kmp可以做到O(|S|)的复杂度35字符串hash问题六给一个字符串S，求S的最小表示法。对一个字符串，进行如下两种操作：1.把头字符放到尾2.把尾字符放到头不断进行上述2个操作，直到S的字典序达到最小，此时的S是原串的最小表示法比如bbabc，最小表示法是abcbb36字符串hash问题六解法：不断取两个起始位置，用二分hash的方法判断他们的字典序，直到找到字典序最小的表示法。复杂度：O(|S|*log|S|)用贪心方法可以做到O(|S|)37字符串hash问题七给一个字符串S，求S的最长连续重复子串。数据范围：1=|S|=105比如abcabababc的最长连续重复子串是ababab连续重复子串：一个串由某一个子串连续重复拼接而成（这个问题比较难,板书或者稍候再增加ppt放群上）38字符串hash问题七分析复杂度时需要用到这个证明式O(n/1+n/2+n/n)O(nlogn)这个嘛，下周讲！39ThankYou！
