Google 店面不是原题

arteeezy

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

x

找一个subfix of string a 在 string b的prefix相同的部分。
例如 a

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

A是suffix，是后缀不是substring
我打错了字了，抱歉

deidaraho

有点疑惑，所以a的substring是必须跟b的prefix一致对么？那直接两个pointer不行么？为啥要用hash？

匿名用户-ZLCZR *2022-7-21 05:44:02* · 2022-7-21 05:44:02

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

fafnir21

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

匿名用户-U2QU8 *2022-7-20 11:56:24* · 2022-7-20 11:56:24

这是Longest common substring吗？应该用dp就解了吧。

fafnir21

这题可以用rolling hash吧？两个string分别从head和tail扫描，同时计算两个hash，直到相等。用O(n)时间可以解决

orlandowzb

匿名用户发表于 2022-7-19 20:56
这是Longest common substring吗？应该用dp就解了吧。

这个要 prefix 和 subfix。有点不一样

orlandowzb

fafnir21 发表于 2022-7-19 23:23
这题可以用rolling hash吧？两个string分别从head和tail扫描，同时计算两个hash，直到相等。用O(n)时间可以 ...

如果后面的顺序不一样还是可以保证 hash 相等

orlandowzb

可以一个 hash map。
直接左边所有可能的 subfix放进去。这就是 O(n)
然后右边每个可能 prefix 尝试，这就是 O(m)
返回第一个有的

orlandowzb

fafnir21 发表于 2022-7-19 23:50
用不同的计算方式来hash，一边从低位到高位，一边从高位到低位。
u -> u + 26*o -> u + 26*o + 26^2*y
...

应该一个 hash map 就可以了

fafnir21

orlandowzb 发表于 2022-7-19 23:54
应该一个 hash map 就可以了

首先，你需要用O(n^2)空间存所有的suffix或者prefix。
其次，hashmap也是hash，也会有collision。。

orlandowzb

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

Google 店面 不是原题