class Solution:
    def shortestPalindrome(self, s: str) -> str:
        # 1. Reverse the string
        r = s[::-1]
        
        # 2. Iterate through the length of the string
        # We want to find the largest 'i' such that 
        # the prefix of s matches the suffix of r
        for i in range(len(s) + 1):
            # s.startswith(r[i:]) checks if the beginning of s 
            # matches the reversed string minus the first i characters.
            if s.startswith(r[i:]):
                # The part that didn't match (r[:i]) is exactly 
                # the reverse of the suffix we need to add.
                return r[:i] + s
                
        return "" # Should basically never hit here given s starts with s

def shortestPalindrome_rolling_hash(s: str) -> str:
    n = len(s)
    if n == 0: return ""
    
    # Constants for hashing
    base = 29
    mod = 10**9 + 7
    
    forward_hash = 0
    reverse_hash = 0
    power_value = 1
    palindrome_end_index = -1
    
    for i, char in enumerate(s):
        val = ord(char) - ord('a') + 1
        
        # 1. Update Forward Hash:
        # Think of this as adding a term to a polynomial:
        # Hash("abc") = a * base^0 + b * base^1 + c * base^2
        forward_hash = (forward_hash + val * power_value) % mod
        
        # 2. Update Reverse Hash:
        # Think of this as shifting the existing hash and adding the new char at the end:
        # Step 1 "a":   a
        # Step 2 "ab":  a * base + b
        # Step 3 "abc": (a * base + b) * base + c
        reverse_hash = (reverse_hash * base + val) % mod
        
        # 3. Check for Palindrome
        if forward_hash == reverse_hash:
            palindrome_end_index = i
            
        # Update power for the next forward_hash iteration
        power_value = (power_value * base) % mod
        
    # We found the longest palindromic prefix ends at palindrome_end_index
    # The suffix is everything after that
    suffix = s[palindrome_end_index + 1:]
    
    return suffix[::-1] + s