KMP의 일부, computeLPS에 대해서 (KMP)

생각보다 굉장히 쉽다. kmp가 복잡하고 이름이 복잡해보여서 그렇지 기본 틀은 간단하다.

lps는 s라는 문자열이 있을때 각 1개의 문자열에서 순서대로 len(s)까지의 길이를 지나는 동안 각 크기의 문자열에 대해 최대 있을 수 있는 가장 긴 prefix와 suffix가 겹치는 길이를 저장한다.

 

예를 들어 ABCA라는 문자열이 있으면 A, AB,ABC,ABCA라는 문자열을 도는 동안 leng은 0부터 시작해 최대 존재할 수 있을 만큼 길이의 포인터를 가리키게 되고 i는 문자열의 길이를 가리키게 되는 투포인터 방식으로 구하게된다.

 

즉 i가 1부터 시작해 len(s)보다 작은 동안, leng은 0에서 시작하게 되고(존재할 수 있는 겹치는 길이는 최소0이므로)

일치하면 leng를 증가시키고 lps[i]는 leng이 되며, i또한 1을 증가시킨다.

만약 일치하지 않는다면 두가지 방식으로 나눈다. 한가지는 leng이 0일때고 (완전히 일치하지 않을때) 다른 하나는 leng=0이 아니라 그 이전에 일치한적이 있어 그이전 최대길이가 해당하는 길이인지 확인해줘야하기 때문에 leng=lps[leng-1]을 통해 그 이전부분이 일치하는 지 확인해준다.

 

결국 이런 투포인터 방식으로 lps를 쉽게 확인 가능하다.

 

def computeLPS(s, lps):

    leng = 0 

    i = 1

    while i < len(s):

        if s[i] == s[leng]:

            leng+=1

            lps[i] = leng

            i+=1

        else:

            if leng!=0:

                leng = lps[leng-1]

            else:

                lps[i] = 0

                i +=1

    return lps

 

s = "ABCA"

lps = [0]*len(s)

 

r = computeLPS(s,lps)

print(r)