字符串hash以及7大问题I.pptVIP

hash＋二分 下面的问题，都需要用到hash＋二分有哪些信誉好的足球投注网站的方法去解决。 会发现，字符串上的很多的性质，都能满足二分的单调性，而hash的作用是判断两个字符串是否一致。 字符串hash问题四 问题：给一个字符串S，求S的最长回文子串。 比如abcbbabbc的最长回文子串是cbbabbc，bbabb也是回文串，但不是最长的 数据范围： 1＝|S|=10^5 什么是回文串？ 字符串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的方法判断他们的字典序，直到找到字典序最小的表示法。 复杂度：O(|S|*log|S|) 用贪心方法可以做到O(|S|) 字符串hash问题七 给一个字符串S，求S的最长连续重复子串。 数据范围： 1=|S|=10^5 比如 abcabababc 的最长连续重复子串是ababab 连续重复子串：一个串由某一个子串连续重复拼接而成 （这个问题比较难,板书或者稍候再增加ppt放群上） 字符串hash问题七 分析复杂度时需要用到这个证明式 O(n/1+n/2+…+n/n)~O(nlogn) 这个嘛，下周讲！ * Thank You！ * * By peterpan 字符串hash简介 有关字符串hash的 7个问题！ 字符串hash 关于字符串hash，就一句话： 把字符串有效地转化为一个整数 在计算机里，用的是二进制编码。在很多语言里，都是用数字作为数组的下标。因为用数字来存储、表达一个object非常方便。 如果能有一种算法，把每个字符串有效地、”唯一”的映射到每个“不同”的整数，我们就能很好的处理字符串。 hash函数 现在我们希望找到一个hash函数，使得每一个字符串都能够映射到一个整数上 比如hash[i]=(hash[i-1]*p+idx(s[i]))%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映射为一个整数 hash[0]=1，表示 a 映射为1 hash[1]=(hash[0]*p+idx(b))%mod=15，表示 ab 映射为 15 hash[2]=(hash[1]*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，问这些字符串里有多少个不同的字符串