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了。。。。。。估计挂在这题上了 |
|
