求问一道google的面试题

vincent_great 发表于 2024-2-29 23:09
实验了下不行。。。

s = 'aaaaaaabac'

可以啊 j=6 返回True

Remineva 发表于 2024-3-1 04:43
可以啊 j=6 返回True

好像是可以的。。
position-hash的想法太强大了。。

the KMP table below stores the max mathching length up to each index in target. for target="xzxyxyy", table returns [0, 1, 2, 2, 3, 3, 1]. Then apply the table to S just like KMP to find mathcing pattern in S.

in "xzxyxyy", say for index 5, the 2nd "y", given that we have "xyx" match "xzx", g is now 3. then for the 2nd y, we know it should match the y in "xzxy". in "xzxy" y shows up for the first time, but in "xyx" we know y has already appeared, so the matching fails. g reduces to table[g-1]  =2, we continue the KMP searching process



    s="abbad"
    target="xzxyxyy"
    w, w2l=dict(), collections.defaultdict(lambda :[float('-inf')])
    for i,j in enumerate(target):
        w2l[j]+=[i]
        w[i]=len(w2l[j])-1
   
    g, table=0, [0]
    for i in range(1,len(target)):   
        j=target[i]   
        while g:
            k=w2l[target[g]][1]
            if (k>=g and w2l[j][w[i]]-w2l[j][w[i]-1]>g) or (k<g and target[i-g+k]==j):
                    g+=1
                    break   
            g=table[g-1]   
        g+=g==0   
        table+=[g]

补充内容 (2024-03-02 13:22 +08:00):

    s="zyzx"
    target="xzxyxyy"
   
   
    w,w2l=dict(), collections.defaultdict(lambda :[float('-inf')])
    for i,j in enumerate(target):   
        w[i]=i-w2l[j][-1]
        w2l[j]+=[i]
   
   
    g,table=0, [0]
    for i in range(1,len(target)):   
        j=target[i]
  
        while g:
            k=w2l[target[g]][1]
            if (k>=g and w[i]>g) or (k<g and target[i-g+k]==j):
                    g+=1
                    break   
            g=table[g-1]  

        g+=g==0   
        table+=[g]

补充内容 (2024-03-02 13:23 +08:00):

第一次发帖 原来这论坛发了就没法修改阿

补充内容 (2024-03-02 13:27 +08:00):

我发到leetcode了 排版好一点


https://leetcode.com/discuss/int...site-or-Secret-Word

emm。。 怎么排版code

这种题目想要接近On只能hash来做了吧

拧眉横目的手电筒 发表于 2024-3-2 04:28
the KMP table below stores the max mathching length up to each index in target. for target="xzxyxyy" ...

感谢大佬的解答。。。。
研究半天终于看懂了，g增加的两种情况 - 要么字符都从未出现，要么字符的前一个位置相同

这里按照大佬的想法重新写了下

微信用户_5awdg 发表于 2024-3-2 06:10
这种题目想要接近On只能hash来做了吧

前面有大佬的按不同字母的hash解法

vincent_great 发表于 2024-3-1 07:03
你说的滑动窗口怎么用前面的内容计算后面一个，求一些细节？
比如 len(secret) = n，现在计算完encoded ...

当然是从头了，N**2的解法嘛