Leetcode 1392. Longest Happy Prefix [Python]

Leetcode 1392. Longest Happy Prefix [Python]

用KMP的话会在第57/75个tc处TLE. 还需要别的方式，需要滚动哈希。记录下KMP版本。随后是rolling hash

class Solution:
    def longestPrefix(self, s: str) -> str:
        res = [""]
        for idx, char in enumerate(s):
            sus_s = s[:idx+1]
            pos = self.KMP(sus_s, s)
            
            if pos != -1 and pos + idx + 1 == len(s) and sus_s != s:
                res.append(sus_s)
        return res[-1] 
             
            
    def KMP(self, P, S):
        ne = [0]*100010
        m = len(P)
        P = ' ' + P
        n = len(S)
        S = ' ' + S
        j = 0
        res = []
        for i in range(2, m+1):
            while j and P[i] != P[j+1]:
                j = ne[j]
            if P[i] == P[j+1]:
                j += 1
            ne[i] = j
        j = 0
        for i in range(1, n+1):
            while j and S[i] != P[j+1]:
                j = ne[j]
            if S[i] == P[j+1]:
                j += 1
            if j == m:
                res.append( i - j )
                j = ne[j]
        return res[-1]

滚动哈希也会跪，其实仔细回想，KMP对于Pattern串的处理，就是在寻找Pattern串里的最长的Prefix&&Suffix。所以，无脑上KMP的上半段就好。

class Solution:
    def longestPrefix(self, s: str) -> str:
        p = s
        m = len(p)
        
        p = ' ' + p
        
        ne = [0] * 100010
        j = 0
        for i in range(2, m+1):
            while j and p[i] != p[j+1]:
                j = ne[j]
            if p[i] == p[j+1]:
                j += 1
            ne[i] = j
        return s[:j]
    
          
        

分割线

KMP 处理String

n = len(s)
s = ' ' + s
j = 0
for i in range(1, n+1):
	while j and s[i] != p[j+1]:
		j = ne[j]
	if s[i] == p[j+1]:
		j += 1
	if j == m:
		print(i-j, end = ' ')
		j = ne[j]