u**u
发帖数: 668 | 1 有牛人能提供秒懂解释吗？
我从来都绕过，都成心病了。。。。。
跪谢了 |
s****a
发帖数: 794 | 2 哪家面试要是考这种东西就不要去了 同事都是这种天才或者神经病你还往里钻？
面试题至少要在同事里面试试 至少绝大多数的同事要能达到bar的 |
r*****s
发帖数: 1815 | 3 Manacher并不是一个通用的算法，除了求回文。。你还用它干啥。。。它的功能可以用
后缀树或者后缀数组来代替。所以我没仔细研究过。
KMP的预处理是对pattern中的每个i，找到0-i范围内的等于后缀的最大前缀长度（利用
0-i-1范围内已经求得的结论进行"动态规划")，此数组记录为P[]
在pattern和实际字符串比较失配的时候，设pattern失配位置为i，则0-i-1范围内把等
于后缀的最大前缀移动到后缀位置，即从P[i - 1] 1 位置开始继续比较，若再次失
配，则重复。
KMP算法的思想是很清晰的。 |
r*****s
发帖数: 1815 | 4 为了证明不是胡吹大气附上一个刚写的strstr:
https://gist.github.com/anonymous/a949d6a76f6a72432cfc2c3045e5fb4d
: Manacher并不是一个通用的算法，除了求回文。。你还用它干啥。。。它的功能
可以用
: 后缀树或者后缀数组来代替。所以我没仔细研究过。
: KMP的预处理是对pattern中的每个i，找到0-i范围内的等于后缀的最大前缀长度
（利用
: 0-i-1范围内已经求得的结论进行"动态规划")，此数组记录为P[]
: 在pattern和实际字符串比较失配的时候，设pattern失配位置为i，则0-i-1范围
内把等
: 于后缀的最大前缀移动到后缀位置，即从P[i - 1] 1 位置开始继续比较，若
再次失
: 配，则重复。
: KMP算法的思想是很清晰的。
【在 r*****s 的大作中提到】
: Manacher并不是一个通用的算法，除了求回文。。你还用它干啥。。。它的功能可以用
: 后缀树或者后缀数组来代替。所以我没仔细研究过。
: KMP的预处理是对pattern中的每个i，找到0-i范围内的等于后缀的最大前缀长度（利用
: 0-i-1范围内已经求得的结论进行"动态规划")，此数组记录为P[]
: 在pattern和实际字符串比较失配的时候，设pattern失配位置为i，则0-i-1范围内把等
: 于后缀的最大前缀移动到后缀位置，即从P[i - 1] 1 位置开始继续比较，若再次失
: 配，则重复。
: KMP算法的思想是很清晰的。
|
z*********n
发帖数: 1451 | 5
KMP其实不难，理解next数组含义就好。我写过支持通配符?和*的KMP...
Manacher确实没用，面试敢考你投诉他
Morris非常trivial啊，虽然后序比较复杂以外。
btw，以上三个基本100%肯定面试不会让你写代码，你可以提一句表示你知道有这么回
事，展现了你的知识面即可。
【在 u**u 的大作中提到】
: 有牛人能提供秒懂解释吗？
: 我从来都绕过，都成心病了。。。。。
: 跪谢了
|
D**********0
发帖数: 1022 | 6 九章第一节就说了，写strstr不要写kmp，贪心法不考。
面试官看不懂，我特意没学。 |
r*****s
发帖数: 1815 | 7 那我下次有人来onsite就考kmp
: 九章第一节就说了，写strstr不要写kmp，贪心法不考。
: 面试官看不懂，我特意没学。
【在 D**********0 的大作中提到】
: 九章第一节就说了，写strstr不要写kmp，贪心法不考。
: 面试官看不懂，我特意没学。
|
z*********n
发帖数: 1451 | 8
刷盘子也要on-site过才让刷？
【在 r*****s 的大作中提到】
: 那我下次有人来onsite就考kmp
:
:
: 九章第一节就说了，写strstr不要写kmp，贪心法不考。
:
: 面试官看不懂，我特意没学。
:
|
D**********0
发帖数: 1022 | 9 那我就只好学一学了。
【在 r*****s 的大作中提到】
: 那我下次有人来onsite就考kmp
:
:
: 九章第一节就说了，写strstr不要写kmp，贪心法不考。
:
: 面试官看不懂，我特意没学。
:
|
m*f
发帖数: 3078 | 10 坚决不学，估计这种题都是留给那些简历上面写参加过竞赛的人
【在 D**********0 的大作中提到】
: 那我就只好学一学了。
|
|
|
r*****s
发帖数: 1815 | 11 这样，下次有人来onsite，我先给他讲一遍KMP，再让他写
: 坚决不学，估计这种题都是留给那些简历上面写参加过竞赛的人
【在 m*f 的大作中提到】
: 坚决不学，估计这种题都是留给那些简历上面写参加过竞赛的人
|
r*****s
发帖数: 1815 | 12 不会KMP怎么知道刷哪个盘子啊！
: 刷盘子也要on-site过才让刷？
【在 z*********n 的大作中提到】
:
: 刷盘子也要on-site过才让刷？
|
l*******g
发帖数: 84 | |
z*******o
发帖数: 4773 | 14 笨,
那就不去那家公司.坚决不学
【在 D**********0 的大作中提到】
: 那我就只好学一学了。
|
u**u
发帖数: 668 | 15 多谢各位牛牛，看来morris最简单，我决定周末抽空烟酒一下 |
