[알고리즘] LCS(Longest Common Subsequence) with Python

Longest Common Substring을 하다가 함께 해본 예제.

그래서 코드만 간단히 올린다.

def extractMarkedText(target_text, compare_text):

    #: 입력된 두개의 인자를 가지고 테이블을 만들기

    width = len(target_text) + 1

    height = len(compare_text) + 1

    # 테이블 초기화 빈값으로 초기화시키기

    table = [''] * width * height

    def getTable(r, c):

        return table[r * width + c]

    def setTable(r, c, value):

        table[r * width + c] = value

    for i in range(1, height):

        for j in range(1, width):

            if target_text[ j - 1] == compare_text[ i - 1]:

                value = getTable( i - 1, j - 1) + target_text[j - 1]

                setTable(i, j, value)

                continue

            searched_span_lcs = getTable(i - 1, j)

            text_lcs = getTable(i, j - 1)

            if len(searched_span_lcs) > len(text_lcs):

                setTable(i, j, searched_span_lcs)

            else:

                setTable(i, j, text_lcs)

    return getTable(height - 1, width - 1)

span = '''

윤리는 종교, 법, 예절과 유사하지만 인간의 이성에 호소하는 점에서 차이가 있으며,

.... ① 소외 계층 권리 보호 ② 국민 권익 보호 기여 ③ 신속한 정보, 뉴스 제공 ④ ....

개방형 서비스 목록 / 표준 통신 방식 / 정보 호환 방식 / 첨단 정보 통신 기술 .... 에

접속하여 일상생활에 심각한 사회적, 정신적, 육체적 및 금전적 '지장'을 받고 있는

상태.

'''

text = '개인용통신기기가제공하는서비스에몰두하여,일상생활에지장을초래할'

result = extractMarkedText(text, span)

print(result)

# 인신제공서비스에하여일상생활에지장을