google 面经

wujingzhishui

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

同学收到的google面试题，我看了下没想到很好的优化算法，贴上来问下。如何cut一个string，使他cut后每个部分一样，然后求这个部分最

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

26 10:20):
我现在想法是找到这个string长度的公约数，去匹配

yunongfang81

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

zyoppy008

判断首字母 backtacking 加判断是否是约数直接做？

leixiang5

感觉好像是backtracking problem...

daniel_hl

KMP吧，找最大循环周期

1peter

daniel_hl 发表于 2016-9-26 12:55
KMP吧，找最大循环周期

没必要一言不合就KMP吧

kolanery

Google foobar出现过这题....用kmp可过所有的test case.

sauceforge

KMP, 得到pi数组，如果数组长度是l, 可以证明答案就是 l / (l-pi[l]). 时间复杂度O(n).

xihaokai1

还有个思路，把所有的char加起来，substring的长度肯定整除gcd(char和，string长度)

xihaokai1

sauceforge 发表于 2016-9-27 01:33
KMP, 得到pi数组，如果数组长度是l, 可以证明答案就是 l / (l-pi[l]). 时间复杂度O(n).

整除的时候这才对吧，比如反例“ABABA”