狗家实习电面

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

lxc0694 发表于 2017-11-20 02:02
第二题 helper 函数 除了brute force 还有其他方法么。 只能substring前i个字符，然后逐一比较后面每个i le ...

我是这样写的 感觉没用更好的方法了，必须的是O(n)吧每给字母都要查

Corey_Lancer 发表于 2017-11-20 01:21
这个string 必须是重复子串构成么？ 比如abcabcd 能否算有2个abc呢？

不行  这种情况return -1，没用重复子串

RicciWoo 发表于 2017-11-20 01:33
感觉得用DP

hmmmm interesting 可以想一下

jeffztn0816 发表于 2017-11-20 02:43
说错了 如果是0开始的index的话 是len-1-next[len-1]

啊啊啊不会kmp, 之前在做strstr的时候听说了这个算法 太懒了没去管 看来得好好看看
谢谢告知！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

RicciWoo 发表于 2017-11-20 13:19
《Algorithm Design》- Kleinberg & Tardos，第6章DP，P329，第19题，是一个类似的题目，可以参考。

补 ...

哇谢谢！！！

可不可以这样做：用hashmap 然后key是每个字母，value是一个vector存这个字母在string里面出现的位置，然后找到出现次数最少的那个字母，比如
aabbbcccaabbbccc
那么就可以找见a出现的位置分别是0，1，8，9然后遍历这个vector分别check: 1-0 , 8 - 0...调用第一问的函数，直到找见一个就是最小的。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

hychin 发表于 2017-12-3 07:11
不太理解你说的，如果是next[len-1], ABCABCABCABC这个12长的字符串最大前缀后缀长度也还是12，你除一下 ...

之后改了如果是0-index的情况是len-1-next[len-1]，另外最大前缀后缀长度是9，不是12。