Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 접두사이자 접미사이며 문자열 내부에도 등장하는 가장 긴 부분 문자열 찾기

주어진 문자열에서 접두사(prefix)이자 접미사(suffix)이면서 동시에 문자열 내부에도 존재하는 가장 긴 부분 문자열(substring)을 찾는 문제입니다. 만약 조건을 만족하는 부분 문자열이 없다면 -1을 반환해야 합니다.

예를 들어 입력이 "languagepythonlanguageinterestinglanguage"라면, 문자열의 시작과 끝에 모두 등장하고 중간에도 포함된 "language"가 정답이 됩니다.

문제 해결 접근: LPS 배열 활용

이 문제는 KMP(Knuth–Morris–Pratt) 문자열 검색 알고리즘에서 사용되는 LPS(Longest Proper Prefix which is also Suffix) 배열을 활용하면 효율적으로 해결할 수 있습니다. LPS 배열의 각 인덱스에는 해당 위치까지의 부분 문자열에서 '접두사이면서 동시에 접미사'인 가장 긴 부분의 길이가 저장됩니다.

알고리즘 단계

  1. get_lps() 함수를 정의합니다. 이 함수는 문자열을 인자로 받습니다.
  2. n은 문자열의 길이로 설정합니다.
  3. 크기가 n이고 모든 값이 0으로 초기화된 배열 long_pref_suff를 생성합니다.
  4. size := 0, long_pref_suff[0] := 0, i := 1로 초기화합니다.
  5. i < n인 동안 다음을 반복합니다.
    • string[i]와 string[size]가 같다면 → size를 1 증가시키고, long_pref_suff[i] := size로 저장한 뒤 i를 1 증가시킵니다.
    • 같지 않다면 → size가 0이 아닌 경우 size := long_pref_suff[size - 1]로 되돌리고, 그렇지 않으면 long_pref_suff[i] := 0으로 설정한 후 i를 1 증가시킵니다.
  6. 완성된 long_pref_suff 배열을 반환합니다.

메인 로직 처리 순서

  1. long_pref_suff := get_lps(string)으로 LPS 배열을 계산합니다.
  2. n은 문자열의 길이입니다.
  3. long_pref_suff[n - 1]이 0이라면 조건을 만족하는 부분 문자열이 없으므로 -1을 반환합니다.
  4. 인덱스 0부터 n - 1까지 탐색하면서 long_pref_suff[i]가 long_pref_suff[n - 1]과 같다면, 해당 위치에도 동일한 접두사·접미사가 존재한다는 뜻이므로 string[0 : long_pref_suff[i]]를 반환합니다.
  5. 만약 long_pref_suff[long_pref_suff[n - 1] - 1]이 0이라면 더 짧은 후보도 없으므로 -1을 반환합니다.
  6. 그렇지 않다면 string[0 : long_pref_suff[long_pref_suff[n - 1] - 1]]을 반환합니다.

구현 코드 예시

아래 파이썬 코드를 통해 실제 동작을 확인해 보겠습니다.

def get_lps(string):
    n = len(string)
    long_pref_suff = [0 for i in range(n)]
    size = 0
    long_pref_suff[0] = 0
    i = 1
    while (i < n):
        if (string[i] == string[size]):
            size += 1
            long_pref_suff[i] = size
            i += 1
        else:
            if (size != 0):
                size = long_pref_suff[size - 1]
            else:
                long_pref_suff[i] = 0
                i += 1
    return long_pref_suff

def get_longest_substr(string):
    long_pref_suff = get_lps(string)
    n = len(string)
    if (long_pref_suff[n - 1] == 0):
        return -1
    for i in range(0, n - 1):
        if (long_pref_suff[i] == long_pref_suff[n - 1]):
            return string[0:long_pref_suff[i]]
        if (long_pref_suff[long_pref_suff[n - 1] - 1] == 0):
            return -1
        else:
            return string[0:long_pref_suff[long_pref_suff[n - 1] - 1]]

string = "languagepythonlanguageinterestinglanguage"
print(get_longest_substr(string))

입력

"languagepythonlanguageinterestinglanguage"

출력

language

정리

이 알고리즘은 KMP 알고리즘의 실패 함수(preprocessing)와 동일한 원리를 사용하기 때문에 시간 복잡도는 O(n)으로 매우 효율적입니다. 문자열의 길이가 길어져도 선형 시간 안에 답을 찾을 수 있으며, 접두사와 접미사가 겹치는 패턴 분석이 필요한 다양한 문자열 문제에도 응용할 수 있습니다.