s*****1 发帖数: 134 | 1 这题我用了三种方法做:
1) Rabin–Karp, 这个方法大小测试时间上均能通过,但是可能是hash function内部实
现的问题,大测试有三个fail了(我在我的电脑上测试了fail的数据,应该是对的)
2) Boyer-Moore, 这个算法好理解,测试也通过了
3) KMP, 这个算法太复杂,没怎么弄明白,写了书上的code,大数据居然exceed time
limit了.
想问大牛们:
1. 你们做这题时,用Rabin-Karp是不是也遇到我这种情况?
2. KMP不是优于BM嘛,为何会超时?
3. 一般KMP面试考吗?如考,怎么考?
谢谢啦 | d**********x 发帖数: 4083 | 2 KMP常数太大,一般实际应用不多
但是我觉得过数据是没问题的,建议你用那几个没过的数据debug一下是不是死循环了
。。
【在 s*****1 的大作中提到】 : 这题我用了三种方法做: : 1) Rabin–Karp, 这个方法大小测试时间上均能通过,但是可能是hash function内部实 : 现的问题,大测试有三个fail了(我在我的电脑上测试了fail的数据,应该是对的) : 2) Boyer-Moore, 这个算法好理解,测试也通过了 : 3) KMP, 这个算法太复杂,没怎么弄明白,写了书上的code,大数据居然exceed time : limit了. : 想问大牛们: : 1. 你们做这题时,用Rabin-Karp是不是也遇到我这种情况? : 2. KMP不是优于BM嘛,为何会超时? : 3. 一般KMP面试考吗?如考,怎么考?
| P******r 发帖数: 842 | 3 不是大牛,经验如下。
写brute force就能过judge large。KMP可以过的。 | l***i 发帖数: 1309 | 4 I use KMP. Admire to those pass by brute force. | n******n 发帖数: 567 | 5 onsite给我出个brute force,写出bug了。。。。。。估计挂在这题上了 |
|