Rooobin edited 6 年前
题意简要来说就是给定若干个字符串，判断任意一对字符串$(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是不会出现问题的