[백준] 공통 부분 문자열

https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

lcs, lcp 문제로 흔히 불리우는 문제의 장르입니다. 

(dp로 해결)

(이 문제는 longest substring 문제로 잘 알려져있습니다.)

 

우선 문제부터 간단하게 요약하면,

두 string이 input으로 들어오면, 해당하는 두 string의 부분 string중 가장 길이가 긴 것의 문자열 길이를 return 해야합니다. 

 

<Solution>

간단한 그림을 통해 아이디어를 살펴봅시다. 

dp array를 search 하면서 각 가로축과 세로축의 문자가 같아지는 순간 왼쪽 사선방향칸의 number + 1을 해주면 됩니다. 

 

이것이 성립하는 이유는 간단합니다. 위 그림에서 dp[i][j] 칸이 의미하는 바가 s1의 0~i 번째 문자열와 s2의 0~j 번째 문자열의 접미사의 겹치는 길이이기 때문입니다.

예를 들면, 위의 그림에서 b와 b가 만나는 지점인 2를 봅시다. 이 경우는 ab, fghab의 접미사중 가장 긴 ab의 길이인 2가 들어오게 됩니다.

 

이처럼 dp 테이블을 구성해서 문제를 해결할 수 있습니다.

 

실제 구현은 아래와 같습니다.

import sys

s1 = sys.stdin.readline().rstrip()
s2 = sys.stdin.readline().rstrip()

dp_array = [[0] * (len(s2)+1) for _ in range(len(s1)+1)]

ans = 0
for i in range(1, len(s1) + 1):
    for j in range(1, len(s2) +1):
        if s1[i-1] == s2[j-1]:
            dp_array[i][j] = dp_array[i-1][j-1] + 1
            ans = max(ans, dp_array[i][j])
        else:
            continue
print(ans)

 

<참고할만한 것들>

- dp를 이용한 O(nm) time complexity로 해결하는법

https://www.geeksforgeeks.org/longest-common-substring-dp-29/

Longest Common Substring | DP-29 - GeeksforGeeks

 

+ 추가

https://www.acmicpc.net/problem/16908

16908번: 가장 긴 공통 부분 문자열

이 문제의 확장형인 16908을 해결하려 했으나 테스트 케이스들은 맞는것 같은데 현재는 메모리 초과로 돌아가지 않고 있습니다.

 

문자열의 갯수가 몇개든 상관없이 돌아갈 수 있도록 일단은 구현을 해두었는데 2<=N<=10이라 메모리를 덜쓰고 구현이 가능할 것 같습니다. 더불어서 5582번의 문제 상황에서도 241mb정도를 사용하는데 당연히 메모리 초과가 날 것 같습니다. 

 

추후에 해결하면 다시 블로그에 포스팅하도록 하겠습니다. (찾아본 결과 dp말고 다른 알고리즘이나 다른 언어를 써야 할수도 있다 싶습니다.)

https://www.geeksforgeeks.org/suffix-tree-application-5-longest-common-substring-2/

Suffix Tree Application 5 - Longest Common Substring - GeeksforGeeks

 

(위의 dp알고리즘을 N개의 문자열로 확장한 코드)

import sys
import itertools
import copy
n = int(sys.stdin.readline().rstrip())

string_list = [sys.stdin.readline().rstrip() for _ in range(n)]

dp_array = [0] * (len(string_list[-1])+1)
idx_list = []

for s in string_list[-2::-1]:
    dp_array = [copy.deepcopy(dp_array) for _ in range(len(s)+1)]
for s in string_list:
    idx_list.append(list(range(len(s))))

for_loop = [p for p in itertools.product(*idx_list)]

def get_element(table, index):
    for ind, e_ in enumerate(index):
        if ind == 0:
            e__ = table[e_]
        else:
            e__ = e__[e_]
    return e__
def modify_element(table, index, num):
    len_idx = len(index)
    for ind, e_ in enumerate(index):
        if ind == 0:
            e__ = table[e_]
        else:
            if ind == len_idx-1:
                e__[e_] = num
            else: 
                e__ = e__[e_]

ans = 0

for e in for_loop:
    # check if all elements are same
    flag = 0
    tmp = string_list[0][e[0]]
    for i in range(1,len(e)):
        if string_list[i][e[i]] != tmp:
            flag = 1
            break
        else:
            continue
    # if same
    if flag == 0:
        a = get_element(dp_array, e)
        modify_element(dp_array, list(map(lambda x: x+1, e)), a+1)
        ans = max(ans, a+1)

    # not same
    else:
        continue
print(ans)