一道GG Onsite题

题目：有一个字典B，有一个字符串A，在B中找一个最长的字符串是A的subsequence。
LZ用的位并行匹配，在字典中从长到短找每一个字符串判断是否是A的子串。
例如判断 s是否是t:abcba的子序列，以t生成一个m

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

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

面试官当时没挑错，说做的好，下去之后给了个code unclear，心情有点郁闷给大家发个思路开心开心。

onsite 挂了吗？ 就因为这一轮吗？

zyoppy008 发表于 2016-12-15 14:26
onsite 挂了吗？ 就因为这一轮吗？

HR是这么说的

Yuzuka 发表于 2016-12-15 14:27
HR是这么说的

我今天才面的，也是有一轮第三题面的不怎么好

没看懂LZ的思路？能解释一下为什么要这么做吗？

同没看懂，但我猜这个思路是仿照的LC 411？

你要把code写出来，让大家分析一下为何是unclear，只说的思路的话很难讲

刚才想了下，subseq和substr搞混了= =||||各位注意
substr:

mask = collections.defaultdict(lambda:0)
for i, ch in enumerate(t):
        mask[ch] += (1 << i)
    x = mask[s[0]]
for i in xrange(1, len(s)):
        x = (((x & -x) * 2 - 1)) & mask[s[i]]
return x != 0

subseq:

mask = collections.defaultdict(lambda:0)
for i, ch in enumerate(t):
        mask[ch] += (1 << i)
x = mask[s[0]]
for i in xrange(1, len(s)):
        x = (x << 1) & mask[s[i]]
return x != 0

忆梦前尘 发表于 2016-12-15 16:15
同没看懂，但我猜这个思路是仿照的LC 411？

类似BNDM 原来做生信的时候用的

where did you find this question, a site or a book?