首页 > ACM题库 > HDU-杭电 > hdu 2146 The most binary substring-字典树-[解题报告]C++
2013
12-29

hdu 2146 The most binary substring-字典树-[解题报告]C++

The most binary substring

问题描述 :

Everybody knows the number is saved with the binary string in the computer. Now, their have N (1 <= N <= 1000) binary strings I tell you, your task is tell me what is the most binary substring with K (1 <= K <= L) characters in the strings I give you. The length of each string is L (1 <= L <= 60). Output times of the most appearing binary substring.

输入:

Each line will contain three numbers N, L, K.
Following N lines, represent N binary strings.

输出:

Each line will contain three numbers N, L, K.
Following N lines, represent N binary strings.

样例输入:

2 6 3
101011
110101
2 6 4
101011
110101

样例输出:

4
2

Hint
In first case, the most sequence is 101, it appears 4 times. In second case, the most sequence is 1010 or 0101, they all just appear 2 times.

本来是用字典树的 用了很多种优化竟然都超时 那就只好用hash了 对所有的串进行重构 化为64位整型 然后使用位运算枚举所有K长串

 

然后用hash存储 使用线性扫描法  还可以优化

 

代码如下:

 

 

 

解题转自:http://www.cnblogs.com/zhuangli/archive/2008/09/14/1290723.html


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥