s*a
2 楼
哪家面试要是考这种东西就不要去了 同事都是这种天才或者神经病你还往里钻?
面试题至少要在同事里面试试 至少绝大多数的同事要能达到bar的
面试题至少要在同事里面试试 至少绝大多数的同事要能达到bar的
r*s
3 楼
Manacher并不是一个通用的算法,除了求回文。。你还用它干啥。。。它的功能可以用
后缀树或者后缀数组来代替。所以我没仔细研究过。
KMP的预处理是对pattern中的每个i,找到0-i范围内的等于后缀的最大前缀长度(利用
0-i-1范围内已经求得的结论进行"动态规划"),此数组记录为P[]
在pattern和实际字符串比较失配的时候,设pattern失配位置为i,则0-i-1范围内把等
于后缀的最大前缀移动到后缀位置,即从P[i - 1] 1 位置开始继续比较,若再次失
配,则重复。
KMP算法的思想是很清晰的。
后缀树或者后缀数组来代替。所以我没仔细研究过。
KMP的预处理是对pattern中的每个i,找到0-i范围内的等于后缀的最大前缀长度(利用
0-i-1范围内已经求得的结论进行"动态规划"),此数组记录为P[]
在pattern和实际字符串比较失配的时候,设pattern失配位置为i,则0-i-1范围内把等
于后缀的最大前缀移动到后缀位置,即从P[i - 1] 1 位置开始继续比较,若再次失
配,则重复。
KMP算法的思想是很清晰的。
r*s
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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: Manacher并不是一个通用的算法,除了求回文。。你还用它干啥。。。它的功能可以用
: 后缀树或者后缀数组来代替。所以我没仔细研究过。
: KMP的预处理是对pattern中的每个i,找到0-i范围内的等于后缀的最大前缀长度(利用
: 0-i-1范围内已经求得的结论进行"动态规划"),此数组记录为P[]
: 在pattern和实际字符串比较失配的时候,设pattern失配位置为i,则0-i-1范围内把等
: 于后缀的最大前缀移动到后缀位置,即从P[i - 1] 1 位置开始继续比较,若再次失
: 配,则重复。
: KMP算法的思想是很清晰的。
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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: Manacher并不是一个通用的算法,除了求回文。。你还用它干啥。。。它的功能可以用
: 后缀树或者后缀数组来代替。所以我没仔细研究过。
: KMP的预处理是对pattern中的每个i,找到0-i范围内的等于后缀的最大前缀长度(利用
: 0-i-1范围内已经求得的结论进行"动态规划"),此数组记录为P[]
: 在pattern和实际字符串比较失配的时候,设pattern失配位置为i,则0-i-1范围内把等
: 于后缀的最大前缀移动到后缀位置,即从P[i - 1] 1 位置开始继续比较,若再次失
: 配,则重复。
: KMP算法的思想是很清晰的。
D*0
6 楼
九章第一节就说了,写strstr不要写kmp,贪心法不考。
面试官看不懂,我特意没学。
面试官看不懂,我特意没学。
l*g
13 楼
KMP 别人推荐的,网上有一个人写的BLOG,非常清晰易懂。
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
u*u
15 楼
多谢各位牛牛,看来morris最简单,我决定周末抽空烟酒一下
相关阅读
请推荐个安全的电子信箱关于recruiter 通过liinkedin联系的问题。给新人普及一下老印职业生涯流程有做SAP ERP 之类的吗 貌似很火吗?也不是每个人都要转码工请教一个面试中的常见问题CMU的校长,什么命阿。泥马印度3哥出身,40年前在路上小便的料子OPT 申请 I-765 表格的签字日期是否可以在I-20签字日期之后女生有卡有经验,但是湾区材料方向工作真心难找啊。。。G现在到底还肯不肯match L和T的offer这个behavioral的问题好难答准备跟800题大牛一起好好搞搞system design了。汉诺塔为啥dfs可以解决?等结果真难熬啊,快2月了两道很有意思的面试题目,大家议一议请推荐combination和permutation的练习题?数学硕士毕业之后,opt期间可以做software developer吗?用求模分组的方法统计IP访问频率最高的那题,不明白,求解惑哪些工业界的research lab作的比较好?(CS领域) (转载)L上有个researcher说要谈谈 给100块 30mins 有人试过