13506번: 카멜레온 부분 문자열

문제 출처 : https://www.acmicpc.net/problem/13506

 

언어 : Kotlin

 

문제 설명 :

문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다.

문자열 S가 주어졌을 때, 카멜레온 부분 문자열을 구하는 프로그램을 작성하시오.

예를 들어, S = "fixprefixsuffix"와 같은 경우에는 "fix"는 접두사, 접미사도 되고, 두 경우가 아닌 위치에도 등장하는 부분 문자열로도 등장한다.

 

입력 :

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져있으며, 길이는 106을 넘지 않는 자연수이다.

 

출력 :

가능한 카멜레온 부분 문자열 T 중에서 길이가 가장 긴 것을 출력한다. 만약, T가 존재하지 않으면 -1을 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
fixprefixsuffix	fix
abcdabc	-1
qwertyqwertyqwerty	qwerty
papapapap	papap

 

풀이 : 

문제의 카멜레온 문자열(접두사와 접미사가 될 수 있고, 접두사 접미사 사이에도 존재하는 문자열)을 얻기 위해 KMP 알고리즘의 접두, 접미, 경계를 이용해 일치하는 부분을 찾고 배열을 만들어 저장하는 makeTable. 주로 pi(부분 일치 테이블)라고 불리는 것을 사용한다.

 

해당 테이블을 통해 접두사와 접미사가 될 수 있는 최대 길이 문자열을 구한다. 이후, 사이에 있는 문자열의 유무를 체크한다. 이를 위해 아호코라식 알고리즘에서 사용되는 실패 링크 개념을 사용한다.

 

https://pangtrue.tistory.com/305

[알고리즘] 아호 코라식(Aho-Corasick) 알고리즘

 

위 글에서 발췌한 부분으로 알아보자.

아호 코라식은 Trie 자료구조를 사용하므로 다음을 향하는 노드가 여러개인 상태임을 기억하자.

트라이에서의 매칭 과정

트라이에서 매칭 중 실패한 상황

매칭에 실패했을 땐 그 전까지 일치한 문자열의 접두사-접미사가 같은 지점으로 이동

 

우리가 풀고 있는 문제는 단순히 주어진 문자열 하나로 판가름 하는 것이기 때문에 저렇게 루트부터 노드가 여러개 나뉘는 것이 아니라, 하나의 직선 길에서만 이뤄진다고 보면 된다.

 

root(c) -> a -> b -> a -> b -> a -> c -> d -> a

위처럼 해당하는 문자가 없으면 포인터를 롤백시킨다.

포인터가 롤백되는 경우 포인터는 매칭 실패 이전까지의 일치 문자열 중 접두사와 접미사가 같은 지점으로 롤백된다.

 

이러한 실패 링크 개념을 이용해 접미사, 접두사에 포함되면서 해당 부분문자열 중 '가장 긴 접미사'부터 순차대로 재귀 탐색한다.

 

 

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val s = readLine()
    val pi = makeTable(s)

    var pattern = ""
    var len = pi[s.length - 1]
    out@ while (len > 0) {
        for (i in 1 until s.length - 1) {
            if (pi[i] == len) {
                pattern = s.substring(i - len + 1, i + 1)
                break@out
            }
        }

        len = pi[len - 1]
    }

    if (pattern.isEmpty()) bw.write("-1") else bw.write(pattern)
    bw.flush()
    bw.close()
}

fun makeTable(pattern:String):IntArray{
    val patternSize = pattern.length
    val table = IntArray(patternSize)

    var j = 0
    for(i in 1 until patternSize) {
        while(j > 0 && pattern[i]!=pattern[j]) {
            j = table[j - 1]
        }
        if(pattern[i] == pattern[j]) {
            table[i] = ++j
        }
    }

    return table
}