We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#!/bin/python3importmathimportosimportrandomimportreimportsys## Complete the 'maxValue' function below.## The function is expected to return an INTEGER.# The function accepts STRING t as parameter.#defmaxValue(t):# Write your code heren=len(t)sa=suffix_array(t,n)lcp=lcp_array(t,sa,n)ans=nleft,right=[-1]*n,[n]*ns=[0]foriinrange(1,n):whilesandlcp[s[-1]]>=lcp[i]:s.pop()ifs:left[i]=s[-1]s.append(i)s=[n-1]foriinrange(n-2,-1,-1):whilesandlcp[s[-1]]>=lcp[i]:s.pop()ifs:right[i]=s[-1]s.append(i)foriinrange(n):ans=max(ans,lcp[i]*(right[i]-left[i]))returnansdefsuffix_array(s,n):sa,l=[[s[i],i]foriinrange(n)],0whilel<2*n:sa.sort(key=lambdax:x[0])last,rank,pos_map=sa[0][0],0,[None]*nforiinrange(n):pos_map[sa[i][1]]=iiflast!=sa[i][0]:last=sa[i][0]rank+=1sa[i][0]=ranknew_tuple=[(sa[i][0],sa[pos_map[sa[i][1]+l]][0]ifsa[i][1]+l<nelse-1)foriinrange(n)]foriinrange(n):sa[i][0]=new_tuple[i]l=1ifnotlelsel<<1return[i[1]foriinsa]deflcp_array(s,sa,n):rank,k,lcp=[None]*n,0,[0]*nforiinrange(n):rank[sa[i]]=iforiinrange(n):ifrank[i]==n-1:k=0continuej=sa[rank[i]+1]whilei+k<nandj+k<nands[i+k]==s[j+k]:k+=1lcp[rank[i]]=kk=max(0,k-1)returnlcpif__name__=='__main__':fptr=open(os.environ['OUTPUT_PATH'],'w')t=input()result=maxValue(t)fptr.write(str(result)+'\n')fptr.close()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
String Function Calculation
You are viewing a single comment's thread. Return to all comments →