TIL 003 LCP/LCS

📕 LCP (Longest common prefix)

👉 사용목적
정렬된 접미사(SA)에서 인접한 접미사들끼리(바로 뒤), 몇 칸까지 겹치를 담은 배열. 반복된 가장 긴 부분 문자열을 빠르게 구할 수 있다.
SA의 응용 배열로 O(N)으로 만들 수 있다.

ex) banana

• 

👉 구현방법
LCP 배열의 특징은 어떤 두 인접한 접미사 X, Y가 있고 그들의 LCP 값이 z(>0)면, X, Y에서 앞의 한 글자씩을 뺀 것 역시 접미사이며, 이들의 LCP 값은 최소 z-1이다.

이를 사용해서 앞에서부터 한글자씩 뺀 접미사의 LCP 값을 구한다

ex) banana
banana -> na -> LCP = 0
anana -> banana -> LCP = 0
nana -> x -> LCP = x
ana -> anana -> LCP = 3(z)
na -> nana -> LCP = 2(z-1)
a -> ana -> LCP = 1(z-1)

👉 링크
아래링크에 자세히 설명되어있다.

접미사배열
https://blog.naver.com/kks227/221028710658

📕 LCS (Longest common subsequence)

👉 사용목적
최장 공통 부분 문자열.
두 단어 중에 겹치는 문자열 중 가장 긴 문자열

👉 구현방법
두 단어를 붙여서 LCP를 구한다.
이 때 두 단어 사이에 '#','$'등의 기호를 섞어 구분 시켜 준다.
LCS는 LCP중 최대값이 아닌, 반대쪽의 글자가 한 글자라도 들어 있는 단어의 LCP 중 최대값이다.
즉, SA에서 인접한 문자열이 반대쪽에 있는 지 확인을 해야한다.

ex)
1. abcdabcdabcd
2. abcds
-> abcdabcdabcd#abcds
LCS = 4 ('abcd')

👉 링크
아래링크에 자세히 설명되어있다.

접미사배열
https://blog.naver.com/kks227/221028710658