Given a string $$s of length $$n$,$ find the longest palindrome that is a substring of $$s in time $(||)$O$(|$s$|).$ You may use copy over the implementation of Ukkonen's algorithm from the notes compute the suffix trie for $$s or the method from the previous problem even though it takes $(||2)$O$(|$s$|2).$

def find$\_$longest$\_$palindrome$($s$)$:

transformed $=\text{'}$#$\text{'}.$join$(\text{'}^\{\}$$$\text{'}.$format$($s$))$ # $^$ and $ are sentinels to avoid boundary issues

n $=$ len$($transformed$)$

P $=[0]*$ n # P$[$i$]$ will hold the radius of the palindrome centered at i

C$,$ R $=0,0$ # C is the center of the rightmost palindrome, R is its right boundary

for i in range$(1,$ n $-1)$: # We don't consider the first and last sentinels

mirror $=2*$ C $-$ i

if i $<$ R:

P$[$i$]=$ min$($R $-$ i$,$ P$[$mirror$])$

while transformed$[$i $+$ P$[$i$]+1]==$ transformed$[$i $-$ P$[$i$]-1]$:

P$[$i$]+=1$

if i $+$ P$[$i$]>$ R:

C$,$ R $=$ i$,$ i $+$ P$[$i$]$

max$\_$len, center$\_$index $=$ max$(($n$,$ i$)$ for i$,$ n in enumerate$($P$))$

start $=($center$\_$index $-$ max$\_$len$)//2$ # Compute the starting index in the original string

return s$[$start:start $+$ max$\_$len$]$

t $=$ find$\_$longest$\_$palindrome$("$ABRACADABRA$$")$

print$($t$)$

assert t $==$ "ADA" or t $==$ "ACA"

IndexError Traceback $($most recent call last$)$ Cell In$[120],$ line $1---->1$ t $=$ find$\_$longest$\_$palindrome$("$ABRACADABRA$$")2$ print$($t$)3$ assert t $==$ "ADA" or t $==$ "ACA" Cell In$[119],$ line $13,$ in find$\_$longest$\_$palindrome$($s$)10$ if i $<$ R: $11$ P$[$i$]=$ min$($R $-$ i$,$ P$[$mirror$])--->13$ while transformed$[$i $+$ P$[$i$]+1]==$ transformed$[$i $-$ P$[$i$]-1]$: $14$ P$[$i$]+=116$ if i $+$ P$[$i$]>$ R: IndexError: string index out of range

how do i fix this so that it takes into account the $ signs at the end of the abracadabra?