谷歌电面挂经

出的题是：find the most frequent repeating substring that appears at least 3 times.
例子： aaaaabc > aaa
aaabc > a

我一开始用了brute force O(N^3)
优化到了 O(N^2)
后来我想了想，其实是能做到 O(N)
最优解和我的答案差不多。我做题太慢了。如果做快一点可以优化到位

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

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

3-10-04 06:09 +08:00):
这个substring里面必须都是同样的字母

应该是the longest repeating substring吧？如果是the most frequent repeating substring，第一个case答案就应该是a了吧，出现了5次

题号1044？被问到hard了 move on 吧 不预先知道Rabin-Karp很难现场弄出来

SinclairDong 发表于 2023-9-30 19:10
fixed-size sliding window 明显是O(N^2）吧。。。。你有N个size的Windows然后。。每个Windows你要slide ...

找重复三次（或者k次）、长度固定的最长的fixed size substring，都是可以通过rolling hash达到接近O(N)的复杂度的（如果忽略大数计算+取模带来的额外复杂度）。

把以上过程记作 verify(猜测长度），通过二分猜测最长substring的长度可以O(NlogN)解出来。


写了下代码，应该能处理10的5次方这样的输入数据范围（string长度）。要求最长substring的话把输出小改一下就好了。

感觉这就是一个fixed-size sliding window的O(N)题

xiaoqiangqlc 发表于 2023-09-30 15:28:59
应该是the longest repeating substring吧？如果是the most frequent repeating substring，第一个case答案就应该是a了吧，出现了5次

对的，我写错了😄

这不就是easy难度的。。

slowloris 发表于 2023-9-30 15:27
感觉这就是一个fixed-size sliding window的O(N)题

fixed-size sliding window 明显是O(N^2）吧。。。。你有N个size的Windows然后。。每个Windows你要slide最多N次。。。

O(N) 应该用suffix tree来做吧。。找那个最深的。。并且生了三胎的那个。

这是easy吧，统计连续重复就可以吧。O（n）

请问是1044么？