Submission #64091953

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def manacher(S):
    C = []
    for a in S:
        C.append(a)
        C.append(0)
    C.pop()
    L = len(C)
    R = [0]*L
    i = j = 0
    while i < L:
        while j <= i < L-j and C[i-j] == C[i+j]:
            j += 1
        R[i] = j
        k = 1
        while j-R[i-k] > k <= i < L-k:
            R[i+k] = R[i-k]
            k += 1
        i += k; j -= k
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

def manacher(S):
    C = []
    for a in S:
        C.append(a)
        C.append(0)
    C.pop()

    L = len(C)

    R = [0]*L

    i = j = 0
    while i < L:
        while j <= i < L-j and C[i-j] == C[i+j]:
            j += 1
        R[i] = j
        k = 1
        while j-R[i-k] > k <= i < L-k:
            R[i+k] = R[i-k]
            k += 1
        i += k; j -= k

    for i in range(L):
        if i & 1 == R[i] & 1:
            R[i] -= 1
    return R


def f(S):
    if S==S[::-1]:
        return True
    return False

S=input()
M=len(S)

A=manacher(S)
#print(A)
N=len(A)
res=1
for i in range(N):
    if i%2:
        m=(i-1)//2
        if (M-m-1)*2==A[i]:
            res=max(res,A[i])
        
        
    else:
        m=i//2
        if M-1-m==A[i]//2:
            res=max(res,A[i])
            
T=S[:-res]
print(S+T[::-1])
        

    
    

    
    
    
    

Submission Info

Judge Result