数据结构 1047 密码碰撞题解

Rooobin edited 1 年,8 月前

题意简要来说就是给定若干个字符串,判断任意一对字符串$(s_i, s_j)$,其中满足$s_j是s_i$的子串的对数,题中所说的有序只是为了避免重复计算,比如

5
mir
mirta
ta
ir
t

其中满足题意的有6
(mir, ir)
(mirta, mir)
(mirta, ta)
(mirta, ir)
(mirta, t)
(ta, t)

首先第一想法肯定是暴力的记录每一个字符串的子串,然后再遍历每一个字符串,判断它与多少个子串相等,那么来估计一些暴力的时间复杂度,记字符串长度为m,子串的个数(不包括空和自己)为$2^m-2$,总共子串个数就是$(2^m-2)n$,再n次遍历,总时间复杂度为$O(n^2(2^m-2))$,本题m最大为10,n最大为20000,那么最差情况下,可能到$10^{11}$,显然是会超时的。

主要问题就在于子串个数太多,n个字符串依次去比较太过复杂,那么如何优化这个比较过程呢,人在做,天在看,哈希大法保平安

哈希的主要作用是把字符串映射为一个整数,这样你就可以将唯一标识某一字符串的整数存到数组中,并用数组值表示出现的次数,那最后计算时,直接把待比较的字符串做同样的哈希处理,得到他在数组中的值即是满足题意的对数

int hash(){
    ...
}
substrings[hash(substr)] = cnt      //hash()为哈希函数

哈希处理有若干注意事项,比如要确保唯一性来避免碰撞等,在此不赘述,大家自行上网查询

当然如果你了解C++的STL,那么就更容易了,利用map可以直接得到子串和int的一一映射,其他都不用担心了

map<string, int> MAP;
MAP[substr] = cnt

如上的处理大大降低了最后比较计算的复杂度,其中第一种降为$O(1)$,第二种为$O(log(N))\ \ (N为子串个数)$,不会超时了

注:

分析,使用哈希函数映射为一个整数时,必须保证要一一对应,那么处理碰撞可能会比较耗时,最后查询时也要考虑碰撞处理带来的相应影响,大家可以研究研究

使用map是不会出现问题的

Comments

你当前正在回复 博客/题目
存在问题!