A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).
Given a string s. Return the longest happy prefix of s .
Return an empty string if no such prefix exists.
 
Example 1:
Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".

Example 2:
Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.

Example 3:
Input: s = "leetcodeleet"
Output: "leet"

Example 4:
Input: s = "a"
Output: ""

 
Constraints:

1 <= s.length <= 10^5
s contains only lowercase English letters.

Difficulty: interview

Starter code:

class Solution:
    def longestPrefix(self, s: str) -> str:
        

Solutions:
class Solution:
    def longestPrefix(self, strn: str) -> str:
        max_prefs = [0]*len(strn)

        curr = 0
        for idx in range(1, len(strn)):
            while True:
                if curr == 0:
                    if strn[idx] == strn[0]:
                        curr = 1
                    max_prefs[idx] = curr
                    break
                else:
                    if strn[idx] == strn[curr]:
                        curr += 1
                        max_prefs[idx] = curr
                        break
                    else:
                        curr = max_prefs[curr-1]

        return strn[:max_prefs[-1]]

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        lps = [0] * n
        j = 0
        for i in range(1, n):
            if s[i] == s[j]:
                j += 1
                lps[i] = j
            else:
                while j > 0:
                    j = lps[j-1]
                    if s[j] == s[i]:
                        j += 1
                        break
                lps[i] = j
        return s[:lps[-1]]

from collections import defaultdict

class TrieNode:
    def __init__(self, x=None):
        self.val = x
        self.end = False
        self.children = defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root = TrieNode()
        self.max_len = 0
    
    def insert(self, word):
        node = self.root
        for i, w in enumerate(word):
            node.children[w].val = w
            node = node.children[w]
            self.root.children[w] = node
            if i == len(w) - 1:
                node.end = True
    
    def find(self, word):
        node = self.root
        d = 0
        for w in word[:-1]:
            print(w, node.children.keys())
            node = node.children[w]
            d += 1
            if node.end:
                print(node.val, node.end)
                self.max_len = max(self.max_len, d)
    
class Solution:
    def longestPrefix(self, s):
        res, l, r, mod = 0, 0, 0, 10**9 + 7
        for i in range(len(s) - 1):
            l = (l * 128 + ord(s[i])) % mod
            r = (r + pow(128, i, mod) * ord(s[~i])) % mod
            if l == r: res = i + 1
        return s[:res]

class Solution:
    def longestPrefix(self, s):
        # res stores the index of the end of the prefix, used for output the result
        # l stores the hash key for prefix
        # r stores the hash key for suffix
        # mod is used to make sure that the hash value doesn't get too big, you can choose another mod value if you want.
        res, l, r, mod = 0, 0, 0, 10**9 + 7

        # now we start from the beginning and the end of the string
        # note you shouldn't search the whole string! because the longest prefix and suffix is the string itself
        for i in range(len(s) - 1):

            # based on an idea that is similar to prefix sum, we calculate the prefix hash in O(1) time.
            # specifically, we multiply the current prefix by 128 (which is the length of ASCII, but you can use another value as well)
            # then add in the ASCII value of the upcoming letter
            l = (l * 128 + ord(s[i])) % mod

            # similarly, we can calculate the suffix hash in O(1) time.
            # Specifically, we get the ith letter from the end using s[~i], note ~i is -i-1
            # we find the pow(128, i, mod) and multiply by the letter's ASCII value
            # Actually, if we don't care about the beautifulness of the code, you can have a variable to keep track of pow(128, i, mod) as you increase i
            r = (r + pow(128, i, mod) * ord(s[~i])) % mod

           # we check if the prefix and suffix agrees, if yes, we find yet another longer prefix, so we record the index
            if l == r: res = i + 1

       # after we finish searching the string, output the prefix
        return s[:res]

class Solution:
    def longestPrefix(self, s):
        # res stores the index of the end of the prefix, used for output the result
        # l stores the hash key for prefix
        # r stores the hash key for suffix
        # mod is used to make sure that the hash value doesn't get too big, you can choose another mod value if you want.
        num_chars = 26
        res, l, r, mod = 0, 0, 0, 10**9 + 7

        # now we start from the beginning and the end of the string
        # note you shouldn't search the whole string! because the longest prefix and suffix is the string itself
        for i in range(len(s) - 1):

            # based on an idea that is similar to prefix sum, we calculate the prefix hash in O(1) time.
            # specifically, we multiply the current prefix by num_chars (which is the length of ASCII, but you can use another value as well)
            # then add in the ASCII value of the upcoming letter
            l = (l * num_chars + ord(s[i])) % mod

            # similarly, we can calculate the suffix hash in O(1) time.
            # Specifically, we get the ith letter from the end using s[~i], note ~i is -i-1
            # we find the pow(num_chars, i, mod) and multiply by the letter's ASCII value
            # Actually, if we don't care about the beautifulness of the code, you can have a variable to keep track of pow(num_chars, i, mod) as you increase i
            r = (r + pow(num_chars, i, mod) * ord(s[~i])) % mod

           # we check if the prefix and suffix agrees, if yes, we find yet another longer prefix, so we record the index
            if l == r: res = i + 1

       # after we finish searching the string, output the prefix
        return s[:res]

class Solution:
    def longestPrefix(self, s: str) -> str:
        '''
        res keeps track of the index of the end of the prefix, used to output the happy prefix
        l stores the hash key for prefix
        r tracks the hash key for suffix
        '''
        res, l, r = 0, 0, 0
        mod = 10**9 + 5 # used to ensure that the hash value doesn't overflow
        '''
        now start from the beginning and end of the string
        - note you shouldn't search teh whole string because the longest prefix/suffix is the string itself
        '''
        for i in range(len(s)-1):
            # hash the prefix/suffix in o(1); 128 can be substituted with any value; it just happens to be the length of ASCII
            '''
            for a given string 'elkmmmelk', prefix elk will be hashed in ascending order.
            e: 'e': hash[e] = ord(e)
            l: 'el': hash[el] = hash(e)*128 + ord(l)
            k: 'elk': hash[elk] = hash(el)*128 + ord(k)
            which translates to (l * 128 + ord(s[i]))

            suffix elk will be hashed in descending order
            k: 'k': hash[k] = ord(k)
            l: 'lk': hash[lk] = ord(k) + ord(l) * 128
            e: 'elk': hash[elk] = ord(k) + ord(l) * 128 + ord(e) * 128^2
            which translates to r + pow(128, i, mod)
            '''
            l = (l * 128 + ord(s[i])) % mod
            r = (r + pow(128, i, mod) * ord(s[-i-1])) % mod
            if l == r: # if both hash values match, update res
                res = i + 1
        return s[:res]

class Solution:
    def longestPrefix(self, s):
        res, l, r, mod = 0, 0, 0, 10**9 + 7
        for i in range(len(s) - 1):
            l = (l * 128 + ord(s[i])) % mod
            r = (r + pow(128, i, mod) * ord(s[~i])) % mod
            if l == r:
                res = i + 1
        return s[:res]

class Solution:
    def longestPrefix(self, s: str) -> str:
        best = ''
        
        left = 0
        right = len(s) - 1
        
        left_s = ''
        right_s = ''
        
        hash_left = 0
        hash_right = 0
        
        while left < len(s) - 1 and right > 0:
            hash_left += ord(s[left])
            hash_right += ord(s[right])
            
            left_s += s[left]
            right_s = s[right] + right_s
            
            if hash_left == hash_right:
                if left_s == right_s:
                    best = left_s
            
            left += 1
            right -= 1
        
        return best


class Solution:
    def longestPrefix(self, s: str) -> str:
        ans = ''
        l, r = 0, 0
        mod = 10**9 + 7
        for i in range(len(s) - 1):
            l = (l * 31 + ord(s[i])) % mod
            r = (r + ord(s[len(s) - i - 1]) * pow(31, i, mod)) % mod
            if l == r:
                ans = s[:i + 1]
        return ans

class Solution:
    def longestPrefix(self, st: str) -> str:
        a = st
        l = len(a)
        leng = 0
        lps = [0]
        i = 1
        while i < l:
            if a[i] == a[leng]:
                leng += 1
                lps.append(leng)
                i += 1
            else:
                if leng > 0:
                    leng = lps[leng - 1]
                else:
                    lps.append(0)
                    i += 1
        return st[:lps[-1]]

class Solution:
    def longestPrefix(self, s: str) -> str:
        ans = ''
        l, r = 0, 0
        mod = 10**9 + 7
        for i in range(len(s) - 1):
            l = (l * 31 + ord(s[i])) % mod
            r = (r + ord(s[len(s) - i - 1]) * pow(31, i, mod)) % mod
            if l == r and s[: i + 1] == s[len(s) - i - 1:]:
                ans = s[:i + 1]
        return ans

class Solution:
    def longestPrefix(self, s: str) -> str:
        ls = len(s)
        id = -1
        for i in range(ls-1):
            if s[0:i+1] == s[ls-i-1:ls]:
                id = i
        return s[:id+1]


class Solution:
    def longestPrefix(self, s: str) -> str:
        ans = 0
        for l in range(len(s)):
            if s[:l] == s[-l:]:
                ans = l
        
        return s[:ans]

class Solution:
    def longestPrefix(self, s: str) -> str:
        
        max_index = -1
        
        for index, _ in enumerate(s[:-1]):
            
            if s[:index+1] == s[-1*(index+1):]:
                max_index = index
        
        return s[:max_index+1]

class Solution:
    def longestPrefix(self, s: str) -> str:
        i,j,l=0,1,len(s)
        m=0
        while(i<l-1):
            if(s[0:i+1]==s[l-i-1: ]):
                m=i+1
                #print(\"i=\",i,s[0:i+1],\" \",s[l-i-1: ])
            i+=1
        if(m==l-1):
            return s[ :l-1]
        else:
            return s[0:m]
                
                


class Solution:
    def longestPrefix(self, s: str) -> str:
        solution = ''
        for i in range(len(s)):
            prefix = s[0:i]
            suffix = s[-len(prefix):]
            if prefix == suffix:
                solution = prefix
        return solution

class Solution:
    def longestPrefix(self, s: str) -> str:
        if len(s) < 2:
            return ''
        length = len(s)
        res = ''
        for i in range(len(s) - 1):
            if s[ : i + 1] == s[length - i - 1 : ]:
                res = s[ : i + 1]
        return res

class Solution:
    def longestPrefix(self, s: str) -> str:
        answer = ''

        for n in range(1,len(s)):
            prefix = s[:n]
            suffix = s[-n:]

            if prefix  == suffix:
                answer = prefix

        return answer

class Solution:
    def longestPrefix(self, s: str) -> str:
        long = 0
        for x in range(0,len(s)-1):
            # print(s[0:x+1] ,s[len(s)-1-x:])
            # print(s[0:x+1]==s[len(s)-1-x:])
            if s[0:x+1]==s[len(s)-1-x:]:
                long = max(long, len(s[0:x+1]))
                # print(long)
        return s[:long]

class Solution:
    def longestPrefix(self, s: str) -> str:
        res = ''
        i, j = 0, len(s) - 1
        while i < len(s)-1:
            if s[:i+1] == s[j:]:
                res = s[:i+1]
            i += 1
            j -= 1
        return res


class Solution:
    def longestPrefix(self, s: str) -> str:
        #KMP
        lps = [0] * len(s)
        j = 0
        for i in range(1, len(s)):
            while j > 0 and s[j] != s[i]:
                j = lps[j - 1]
            if s[j] == s[i]:
                lps[i] = j + 1
                j += 1
        return s[:lps[-1]]


class Solution:
    def longestPrefix(self, s: str) -> str:
        long = 0
        for x in range(0,len(s)-1):
            a = s[0:x+1]
            b = s[len(s)-1-x:]
            if a==b:
                long = max(long, len(a))
        return s[:long]

class Solution:
    def longestPrefix(self, s: str) -> str:
        long = 0
        for x in range(0,len(s)-1):
            if s[0:x+1]==s[len(s)-1-x:]:
                long = max(long, len(s[0:x+1]))
        return s[:long]

class Solution:
    def longestPrefix(self, s: str) -> str:
        i=0
        string=str()
        ans=0
        j=len(s)-1
        while i<len(s)-1 and j>0:
            if s[0:i+1]==s[j:len(s)]:
                if i+1>ans:
                    ans=i+1
                    string=s[0:i+1]
            i=i+1
            j=j-1
        return string


class Solution:
    def longestPrefix(self, s: str) -> str:
        ans=''
        for i in range(len(s)):
            if s[:i]==s[-i:] and len(s[:i])>=len(ans):
                ans=s[:i]
        return ans

class Solution:
    def longestPrefix(self, s: str) -> str:
        result = ''
        
        left = 0
        right = len(s) - 1
        
        hash_left = 0
        hash_right = 0
        
        while left < len(s) - 1 and right > 0:
            # hash_left += ord(s[left])
            # hash_right += ord(s[right])
            
            # if hash_left == hash_right:
            if s[:left + 1] == s[right:]:
                result = s[right:]
            
            left += 1
            right -= 1
        
        return result


class Solution:
    def longestPrefix(self, s: str) -> str:
#         prefixes = []
#         for i in range(1, len(s)):
#             prefixes.append(s[0:i])
            
#         # print(prefixes)
        
        
#         suffixes = []
#         for i in range(1, len(s)):
#             suffixes.append(s[len(s)-i:])
        
#         # print(suffixes)
        
#         common = set(prefixes).intersection(set(suffixes))
        
#         # print(common)
        
#         ans = ''
#         for s in common:
#             if len(s) > len(ans):
#                 ans = s
#         return ans 
        i = 1
        ans = ''
        while i < len(s):
            # print(s[0:i], s[len(s)-i:])
            if s[0:i] == s[len(s)-i:]:
                ans = s[0:i]
            i += 1
        return ans
                


class Solution:
    def longestPrefix(self, s: str) -> str:
#         n = len(s)
#         r = -1
#         i = 0
#         while i < (n-1):
#             if s[0:(i+1)] == s[(n-i-1):]:
#                 r = i
#             i += 1
#             if i >= (n-1):
#                 break

        
#         return s[0:(r+1)]
    
        res, l, r, mod = 0, 0, 0, 10**9 + 7

        # now we start from the beginning and the end of the string
        # note you shouldn't search the whole string! because the longest prefix and suffix is the string itself
        for i in range(len(s) - 1):

            # based on an idea that is similar to prefix sum, we calculate the prefix hash in O(1) time.
            # specifically, we multiply the current prefix by 128 (which is the length of ASCII, but you can use another value as well)
            # then add in the ASCII value of the upcoming letter
            l = (l * 128 + ord(s[i])) % mod

            # similarly, we can calculate the suffix hash in O(1) time.
            # Specifically, we get the ith letter from the end using s[~i], note ~i is -i-1
            # we find the pow(128, i, mod) and multiply by the letter's ASCII value
            # Actually, if we don't care about the beautifulness of the code, you can have a variable to keep track of pow(128, i, mod) as you increase i
            r = (r + pow(128, i, mod) * ord(s[~i])) % mod

           # we check if the prefix and suffix agrees, if yes, we find yet another longer prefix, so we record the index
            if l == r: res = i + 1

       # after we finish searching the string, output the prefix
        return s[:res]

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        i = 0
        maxi = ''
        while i<n:
            print()
            if s[:i] == s[n-i:]: 
                maxi = max(maxi, s[:i])
            i += 1
        print('maxi', maxi)
        return maxi

class Solution:
    def longestPrefix(self, s: str) -> str:
        best = ''
        
        for i in range(1, len(s)):
            pattern = s[:i]
            if s.startswith(pattern) and s.endswith(pattern):
                best = pattern
        
        return best

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(list(s))
        for i in range(0,n):
            if s[0:i] == s[n-i:n]:
                result = s[0:i]
        return result

class KMP:
    def Build(self, p):
        m = len(p)
        nxt = [0, 0]
        j = 0
        for i in range(1, m):
            while j > 0 and p[i] != p[j]:
                j = nxt[j]
            if p[i] == p[j]:
                j += 1
            nxt.append(j)
            
        return nxt
    
    def Match(self, s, p):
        n = len(s)
        m = len(p)
        nxt = self.Build(p)
        ans = []
        j = 0
        for i in range(n):
            while j > 0 and s[i] != p[j]:
                j = nxt[j]
            if s[i] == p[j]:
                j += 1
            if j == m:
                ans.append(i - m + 1)
                j = nxt[j]
        return ans


class Solution:
    def longestPrefix(self, s: str) -> str:
        kmp = KMP()
        nxt = kmp.Build(s)
        return s[:nxt[-1]]
        


class Solution:
    def longestPrefix(self, s: str) -> str:
        len_s = len(s)
        nxts = [0] * len_s
        i, j = 1, 0
        while i < len_s:
            while s[j] != s[i] and j > 0:
                j = nxts[j - 1] # 退而求其次 考虑 s[:j - 1], 这个算过了是nxt(s[j - 1])
            if s[j] == s[i]: # while stop only two
                j = j + 1 
                nxts[i] = j
            i = i + 1
        return s[len_s-nxts[-1]:]


class Solution:
    def longestPrefix(self, s: str) -> str:
        pre = self.get_pre(s)
        return s[0:pre[-1]]
        
    def get_pre(self, pattern):
        pre = [0]
        n = len(pattern)
        j = 0
        for i in range(1, n):
            while j and pattern[j] != pattern[i]:
                j = pre[j-1]
                
            if pattern[i] == pattern[j]:
                j +=1
            pre.append(j)
        return pre

class Solution:
    def longestPrefix(self, s: str) -> str:
        len_s = len(s)
        nxts = [0] * len_s
        i = 1
        j = 0
        while i < len_s:
            while j > 0 and s[j] != s[i]:
                j = nxts[j - 1] # 退而求其次 考虑 s[:j - 1], 这个算过了是nxt(s[j - 1])
            if s[j] == s[i]: # while stop only two
                j = j + 1 
            nxts[i] = j
            i = i + 1
        return s[len_s-nxts[-1]:]


class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        arr = [0 for i in range(n)]
        
        i = 1
        j = 0
        try:
            while i<n:
                if j==0 and s[i]!=s[j]:
                    arr[i] = 0
                    i+=1
                else:
                    if s[i]==s[j]:
                        arr[i] = j+1
                        i+=1
                        j+=1
                    else:
                        j = arr[j-1]

            return s[:arr[n-1]]
        
        except:
            return i
        
    '''
    a a b a a b a a a
    0 1 2 3 4 5 6 7 8
    0 1 0 1 2 3 4 5 2
    
    '''

class Solution:
    def longestPrefix(self, s: str) -> str:
        
        n = len(s)
        
        lps = [0]*n
        
        for i in range(1, n):
            
            j = lps[i-1]
            
            while j>0 and s[j]!=s[i]:
                j = lps[j-1]
            
            if s[j]==s[i]:
                lps[i] = j+1
        
        
        return s[:lps[n-1]]
            
        
            


class Solution:
    def longestPrefix(self, s: str) -> str:
        def build(p):
            m = len(p)
            nxt = [0,0]
            j = 0
            for i in range(1,m):
                while j > 0 and s[i] != s[j]:
                    j = nxt[j]
                if s[i] == s[j]:
                    j += 1
                nxt.append(j)
            return nxt
        
        nxt = build(s)
        return s[:nxt[-1]]

class Solution:
    def longestPrefix(self, s: str) -> str:
        len_s = len(s)
        nxts = [0]
        i = 1
        j = 0
        while i < len_s:
            while j > 0 and s[j] != s[i]:
                j = nxts[j - 1] # 退而求其次 考虑 s[:j - 1], 这个算过了是nxt(s[j - 1])
            if s[j] == s[i]:
                j = j + 1
            i = i + 1
            nxts.append(j)
        return s[len_s-nxts[-1]:]


class Solution:
    def longestPrefix(self, s: str) -> str:
        len_s = len(s)
        nxts = [0]
        i = 1
        j = 0
        while i < len_s:
            while j > 0 and s[j] != s[i]:
                j = nxts[j - 1] # 退而求其次
            if s[j] == s[i]:
                j = j + 1
            else:
                j = 0
            i = i + 1
            nxts.append(j)
        return s[len_s-nxts[-1]:]


class Solution:
    def longestPrefix(self, s: str) -> str:
        l = len(s)
        nx = [-1] * (l + 1)
        i, j = 0, -1
        while i < l:
            while j == -1 or (i < l and s[i] == s[j]): 
                i += 1
                j += 1
                nx[i] = j
            if i < l and s[i] != s[j]: j = nx[j]
        return s[:nx[-1]]

class Solution:
    def longestPrefix(self, s: str) -> str:
        i, j = 0, -1
        t = [0 for _ in range(len(s)+1)]
        t[0] = -1
        while i < len(s):
            if j == -1 or s[i] == s[j]:
                i += 1
                j += 1
                t[i] = j
            else:
                j = t[j]
        return s[:t[-1]]

class Solution:
    def longestPrefix(self, s: str) -> str:
        
        def build():
            hashtable = [0 for _ in s]
            
            for i in range(1, len(s)):
                j = hashtable[i - 1]
                
                while j > 0 and s[i] != s[j]:
                    j = hashtable[j - 1]
                
                if s[i] == s[j]:
                    hashtable[i] = j + 1
            
            return hashtable
        
        table = build()
        
        return s[len(s) - table[-1]:]

class Solution:
    def longestPrefix(self, s: str) -> str:
        par = [0] * len(s)
        
        for i in range(1, len(s)):
            j = par[i-1]
            while j and s[j] != s[i]:
                j = par[j-1]
            j += int(s[i] == s[j])
            par[i] = j
        
        return s[:par[-1]]

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        pi = [0]*n
        for i in range(1, n):
            j = pi[i - 1]
            while j > 0 and s[j] != s[i]:
                j = pi[j - 1]
            if s[i] == s[j]:
                j += 1
            pi[i] = j
        return s[:pi[n-1]]

class Solution:
    def longestPrefix(self, s: str) -> str:
        
        lps = [0]
        for i in range(1, len(s)):
            pos = lps[-1]
            if s[pos] == s[i]:
                lps.append(1+lps[-1])
            else:
                pos = lps[lps[-1]-1]
                if s[pos] == s[i]:
                    lps.append(1+pos)
                else:               
                    lps.append(0)
        return s[:lps[-1]]

class Solution:
    def longestPrefix(self, st: str) -> str:
        a=st
        l=len(a)
        leng=0
        i=1
        lps=[0]
        while i<l:
            if a[leng]==a[i]:
                leng+=1
                lps.append(leng)
                i+=1
            else:
                if leng>0:
                    leng=lps[leng-1]
                else:
                    lps.append(0)
                    i+=1
        return st[:lps[-1]]


class Solution:
    def longestPrefix(self, s: str) -> str:
        n=len(s)
        LPS=[0]*n
        
        i=1
        longestprefix=0
        while i<n:
            if s[longestprefix]==s[i]:
                longestprefix+=1
                LPS[i]=longestprefix
                i+=1
            else:
                if longestprefix>0:
                    longestprefix=LPS[longestprefix-1]
                else:
                    i+=1
        return s[:LPS[-1]]

class Solution:
    def longestPrefix(self, s: str) -> str:
        lps=[0]*len(s)
        i=1
        l=0
        while(i<len(s)):
            if(s[i]==s[l]):
                l=l+1
                lps[i]=l
                i=i+1
            else:
                if(l):
                    l=lps[l-1]
                else:
                    lps[i]=0
                    i=i+1
        m=lps[-1]
        index=len(s)-1
        #print(lps)
        #for i in range(len(s)):
         #   if(lps[i]>m):
          #      m=lps[i]
           #     index=i
        
        #print(m,index)
        return s[abs(m-index-1):index+1]

class Solution:
    def longestPrefix(self, s: str) -> str:
        t = [-1]
        pos, cnd = 1, 0
        while pos < len(s)-1:
            if s[pos] == s[cnd]:
                t.append(t[cnd])
            else:
                t.append(cnd)
                cnd = t[cnd]
                while cnd >= 0 and s[pos] != s[cnd]:
                    cnd = t[cnd]
            pos += 1
            cnd += 1
        t.append(cnd)
        
        j, k = 1, 0
        while j < len(s):
            if s[k] == s[j]:
                j += 1
                k += 1
                if k == len(s):
                    k = t[k]
            else:
                k = t[k]
                if k < 0:
                    j += 1
                    k += 1
        return s[:k]

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        prefix, suffix = 0, 0
        base, mod, mul = 31, 1000000007, 1
        happy = 0
        for i in range(1, n):
            prefix = (prefix * base + (ord(s[i - 1]) - 97)) % mod
            suffix = (suffix + (ord(s[n - i]) - 97) * mul) % mod
            if prefix == suffix:
                happy = i
            mul = mul * base % mod
        return s[:happy]



MOD = 100000007

class Solution:
    def longestPrefix(self, s: str) -> str:
        
        r = 0
        
        L = R = 0
        multi = 1
        for i in range(len(s)-1):
            L = (26*L + ord(s[i]) - ord('a')) % MOD
            R = ((ord(s[~i]) - ord('a')) * multi + R) % MOD
            multi = multi * 26 % MOD
            if L == R:
                r = i + 1
   
        return s[:r]

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        if(n < 2):
            return ''

        i = 1; j = 0
        f = [0 for _ in range(n)]
        
        while(i < n):
            if(s[i] == s[j]):
                j += 1
                f[i] = j
                i += 1

            elif(j > 0):
                j = f[j - 1]
            
            else:
                i += 1
        return s[:f[-1]]

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        for i in range(1, n):
            if s.startswith(s[i:]):
                return s[i:]
        return ''

class Solution2:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        dp = [[ 0 ] * n for _ in range(n)]
        for i in range(n - 1):
            for j in range(i +1, n):
                if s[i] == s[j]:
                    if i == 0:
                        dp[i][j] = 1
                    elif dp[i-1][j - 1]:
                        dp[i][j] = dp[i-1][j - 1] + 1
        max_len = 0
        for i in range(n): max_len = max(max_len, dp[i][n-1])
        return s[-max_len:] if max_len else ''


class Solution:
  def longestPrefix(self, s: str) -> str:
    # rolling hash
    # use large prime as hash function, pay attention to the possible hash collision.
    # fibonacci primes: 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 
    #  99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917, ..
    M = 19134702400093278081449423917
    n, h, t = len(s), 0, 0
    v = list(map(lambda x: ord(x) - ord('a'), s))
    l, p = 0, 1
    for i in range(n - 1):
      h = (h * 26 + v[i]) % M
      t = (v[n - 1 - i] * p + t) % M
      p = p * 26 % M
      if h == t:
        l = i + 1
    return s[:l]

class Solution:
    MOD = 10 ** 9 + 7
    def longestPrefix(self, s: str) -> str:
        N = len(s)
        left_i, right_i = 0, N - 1
        left_val = right_val = 0
        
        best_left = -1
        right_multiplier = 1
        for i in range(N - 1):
            left_char, right_char = s[i], s[N-i-1]
            left_val = left_val * 26 + (ord(left_char) - ord('a'))
            right_val = (ord(right_char) - ord('a')) * right_multiplier + right_val
            right_multiplier *= 26
            
            left_val %= Solution.MOD
            right_val %= Solution.MOD
            right_multiplier %= Solution.MOD
            if left_val == right_val:
                best_left = i

        return s[:best_left+1]

class Solution:
    def longestPrefix(self, s: str) -> str:
        if len(s) == 1: return ''
        
        def KMPSearch(pat, txt): 
            M, N = len(pat), len(txt) 
            lps = failure(pat)

            i = 0 # index for txt[] 
            j = 0 # index for pat[] 
            while i < N: 
                if pat[j] == txt[i]: 
                    i += 1
                    j += 1
                elif i < N and pat[j] != txt[i]: 
                    if j != 0: 
                        j = lps[j-1] 
                    else: 
                        i += 1
                if i >= N:                        
                    return i - j 

        def failure(pat): 
            res = [0]
            i, target = 1, 0
            while i < len(pat): 
                if pat[i]== pat[target]: 
                    target += 1
                    res += target,
                    i += 1
                elif target: 
                    target = res[target-1] 
                else: 
                    res += 0,
                    i += 1
            return res                        
                        
        l = len(s) - 1 - KMPSearch(s[:-1], s[1:])
        return s[:l]

class Solution:
    def longestPrefix(self, s: str) -> str:
        n=len(s)
        if n<=1: return ''
        
        prefix, suffix,base=0,0,1
        NUM=10**9+7
        ans=''
        for i in range(1,n):
            # i is the length of prefix and suffix
            x=ord(s[i-1])-ord('a')
            prefix=(26*prefix+x) % NUM
            
            x=ord(s[n-i])-ord('a')
            suffix=(suffix+x*base) % NUM
            base=(base*26) % NUM
            
            if prefix==suffix:
                if s[0:i]==s[n-i:n]: ans=s[0:i]
        return ans

class Solution:
    def longestPrefix(self, s: str) -> str:
        result = ''
        
        left = 0
        right = len(s) - 1
        
        hash_left = 0
        hash_right = 0
        
        while left < len(s) - 1 and right > 0:
            hash_left += ord(s[left])
            hash_right += ord(s[right])
            
            if hash_left == hash_right:
                if s[:left + 1] == s[right:]:
                    result = s[right:]
            
            left += 1
            right -= 1
        
        return result


class Solution:
    def longestPrefix(self, s: str) -> str:
        # https://leetcode.com/problems/longest-happy-prefix/discuss/547237/JavaPython-Rolling-Hash
        # https://leetcode.com/problems/longest-happy-prefix/discuss/547446/C%2B%2BJava-with-picture-incremental-hash-and-KMP
        n = len(s)
        prefix = [0]*n
        j, i = 0, 1
        while i < n:
            if s[j] == s[i]:
                j += 1
                prefix[i] = j
            elif j > 0:
                j = prefix[j-1]
                i -= 1
            i += 1
        return s[:j]

class Solution:
    def longestPrefix(self, s: str) -> str:
        best = ''
        
        left = 0
        right = len(s) - 1
        
        
        hash_left = 0
        hash_right = 0
        
        while left < len(s) - 1 and right > 0:
            hash_left += ord(s[left])
            hash_right += ord(s[right])
            
            if hash_left == hash_right:
                if s[:left + 1] == s[right:]:
                    best = s[right:]
            
            left += 1
            right -= 1
        
        return best


class Solution:
    # kmp, time: O(n), space: O(n)
    # build the LPS table; lps: longest proper prefix which is also suffix.
    # lps[i]: for pattern[:i], the longest prefix which is a also the suffix
    def build(self, p):
        leng = 0
        i = 1
        lps = [0]
        while i < len(p):
            if p[i] == p[leng]:
                i += 1
                leng += 1
                lps.append(leng)
            else:
                if leng:
                    leng = lps[leng - 1]
                else:
                    lps.append(0)
                    i += 1
        return lps
    
    def longestPrefix2(self, s: str) -> str:
        lps = self.build(s)
        return s[:lps[-1]]

    
    
    
    # rolling hash
    # for the string of i size, the hash is: s[0] * 26 ^ (i - 1) + s[1] * 26 ^ (i -2) + ... + s[i - 2] * 26 + s[i - 1].
    def longestPrefix(self, s: str) -> str:
        mul = 1; mod = pow(10, 9) + 7
        i = 0; j = len(s) - 1
        res = 0
        hash1 = 0; hash2 = 0
        while i < len(s) - 1 and j > 0:
            hash1 = (hash1 * 26 + ord(s[i]) - ord('a')) % mod
            # s[n-1] -> s[n-2]*26 + s[n-1] -> s[n-3]*26^2 + s[n-2]*26 + s[n-1]
            hash2 = (hash2 + mul * (ord(s[j]) - ord('a'))) % mod 
            mul = mul * 26 % mod
            if hash1 == hash2:
                res = i + 1
            i += 1
            j -= 1
        return s[:res]
            
            


class Solution:
    def longestPrefix(self, s: str) -> str:
        length = len(s)
        for i in range(1, length):
            if s[i] == s[0] and s[i:] == s[:length - i]:
                return s[i:]
        return ''

class Solution:
    def longestPrefix(self, s: str) -> str:
        p1 = s[0]
        length = len(s)
        for i in range(1, len(s)):
            if s[i] == p1:
                if s[i:] == s[:length - i]:
                    return s[i:]
        return ''

class Solution:
    def longestPrefix(self, s: str) -> str:
        p1 = s[0]
        length = len(s)
        for i in range(1, len(s)):
            if s[i] == p1 and s[i:] == s[:length - i]:
                return s[i:]
        return ''

class Solution:
    def longestPrefix(self, s: str) -> str:
        for i in range(len(s)-1,-1,-1):
            if s[:i] == s[-i:]:
                return s[:i]
        return ''

'''
Using Rabin-Karp incremental hash
Reference:
https://leetcode.com/problems/longest-happy-prefix/discuss/547446/C%2B%2BJava-with-picture-incremental-hash-and-KMP
'''
class Solution:
    def longestPrefix(self, s: str) -> str:
        index = 0
        MOD = 10**9 + 7
        mul = 1
        sLen = len(s)
        prefixHash, suffixHash = 0, 0
        j = sLen-1
        
        for i in range(sLen-1):
            first = ord(s[i]) - ord('a')
            last = ord(s[j]) - ord('a')
            prefixHash = (prefixHash*26 + first) % MOD
            suffixHash = (last*mul + suffixHash) % MOD
            mul = (mul*26) % MOD
            j-=1
            if prefixHash == suffixHash:
                index = i+1
        
        return s[:index]


#ababdababc
#0012012340

class Solution:
    def computelps(self, p: str):
        m = len(p)
        lps = [0] * m
        i = 1
        j = 0
        
        while i < m:
            if p[i] != p[j]:
                if j == 0:
                    i += 1
                else:
                    j = lps[j-1]
            else:
                j += 1
                lps[i] = j
                i += 1
        return lps
        
        
    def longestPrefix(self, s: str) -> str:
        lps = self.computelps(s)
        
        return s[:lps[-1]]


class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        k = n - 1
        while k > 0:
          if s[:k] == s[-k:]:
            break
          k -= 1
        return s[:k]

class Solution:
    def longestPrefix(self, st: str) -> str:
        a=st
        l=len(a)
        leng=0
        i=1
        lps=[0]
        while i<l:
            if a[leng]==a[i]:
                leng+=1
                lps.append(leng)
                i+=1
            else:
                if leng>0:
                    leng=lps[leng-1]
                else:
                    lps.append(0)
                    i+=1
        return st[:lps[-1]]

class Solution:
    def longestPrefix(self, s: str) -> str:
        sLen = len(s)
        if sLen == 1:
            return ''
        
        def happyNow(x):
            if s[:x] == s[-x:]:
                return True
            return False 
        
        for length in range(sLen-1, 0, -1):
            if happyNow(length):
                return s[:length]
        return ''

class Solution:
    def longestPrefix(self, st: str) -> str:
        a = st
        l = len(a)
        i = 1
        leng = 0
        lps = [0]
        while i < l:
            if a[i] == a[leng]:
                leng += 1
                lps.append(leng)
                i += 1
            else:
                if leng > 0:
                    leng = lps[leng - 1]
                else:
                    lps.append(0)
                    i += 1
        return st[:lps[-1]]


class Solution:
    def longestPrefix(self, s: str) -> str:
        for i in range(len(s)-1,0,-1):
            # print(s[:i],s[len(s)-i:])
            if s[:i]==s[len(s)-i:]:
                return s[:i]
        return ''

class Solution:
    def longestPrefix(self, s: str) -> str:
        res, l, r, mod = 0, 0, 0, 10**9 + 7

        # now we start from the beginning and the end of the string
        # note you shouldn't search the whole string! because the longest prefix and suffix is the string itself
        for i in range(len(s) - 1):

            # based on an idea that is similar to prefix sum, we calculate the prefix hash in O(1) time.
            # specifically, we multiply the current prefix by 128 (which is the length of ASCII, but you can use another value as well)
            # then add in the ASCII value of the upcoming letter
            l = (l * 128 + ord(s[i])) % mod

            # similarly, we can calculate the suffix hash in O(1) time.
            # Specifically, we get the ith letter from the end using s[~i], note ~i is -i-1
            # we find the pow(128, i, mod) and multiply by the letter's ASCII value
            # Actually, if we don't care about the beautifulness of the code, you can have a variable to keep track of pow(128, i, mod) as you increase i
            r = (r + pow(128, i, mod) * ord(s[~i])) % mod

           # we check if the prefix and suffix agrees, if yes, we find yet another longer prefix, so we record the index
            if l == r: res = i + 1

       # after we finish searching the string, output the prefix
        return s[:res]

class Solution:
    def longestPrefix(self, s: str) -> str:
        res, l, r , mod = 0,0,0, 10**9+7
        for i in range(len(s)-1):
            l = (l*128 + ord(s[i]))%mod
            r = (ord(s[~i])*(pow(128,i,mod)) + r)%mod
            if l==r: res = i+1
        return s[:res ]
        
   
        
        
        
    def longestPrefix_bychance_Brute(self, s: str) -> str:
        res = ''
        for i in range(1, len(s)):
            if s[:i]==s[-i:]:
                res =s[:i]
        return res


class Solution:
  def longestPrefix(self, s: str) -> str:
    j, prefix, suffix = 0, 0, 0
    mod = 10**9 + 9
    for i in range(len(s)-1):
      prefix = (prefix * 128 + ord(s[i])) % mod
      suffix = (suffix + pow(128, i, mod) * ord(s[-i-1])) % mod
      if prefix == suffix:
        j = i + 1
    return s[:j]