[백준/Swift] 1701: Cubeditor | PS일지

문제

1701번: Cubeditor

간단한 문제 요약

  어떤 문자열내에서 같은 부분 문자열이 두 번 이상 나오는 문자열을 찾는데 이때 두 부분 문자열은 겹처도 된다. 가장 길이가 긴 것을 구하는 프로그램을 작성하시오.

문제 풀이,  했갈렸던 점

 주어진 문자열을 pattern 이라 부르겠습니다. 정답은 pattern 내 여러 substring 중 같은 substring 두 개 이상 나와야 합니다. 그 substring은 같은 substring들 중에서 길이가 가장 길어야 합니다.

 

1. pattern에서 만들 수 있는 substring들을 분리한다. 

2. pattern의 모든 문자열.count - substring.count + 1 만큼의 반복문을 통해 pattern의 첫 문자열 부터 substring과 맞는지 비교를 해간다. 일치한다면 카운트를 기록하고 2개 인 경우 다음 substring 도 체크한다.

가장 일반적인 비교 방법입니다.

 

하지만 저는 kmp 알고리즘을 공부했기에 kmp를 활용하면 쉽겠다고 생각했습니다.

kmp 알고리즘을 모르신다면 오른쪽 링크를  ,, (kmp 알고리즘 개념 정리 포스트)

 

kmp알고리즘의 특징은 주어진 문자열 text에서 찾고자 하는 문자열 needle을 비교할 때 needle문자열의 특정 index에서 틀렸다면 0~index-1. 틀린 구간 전까지 비교했고 일치했다는 개념을 이용해서 다음 비교 위치를 바로바로 지정해 jump한다는 개념입니다. 이때 pi배열. 부분 일치 테이블을 사전에 구합니다. 그 이유는 text의 특정 문자 == needle의 특정 문자가 일치하기 때문에 결국 needle의 특정 index에서 prefix == suffix인 구간을 찾아 시작 지점을 손쉽게 정할 수 있다는 점입니다.

 

kmp알고리즘의 pi(부분 일치 테이블) 배열에는 특정 index마다 prefix == suffix 인 문자열 길이 정보를 담고 있습니다. prefix == suffix라는 것은 결국 pattern의 맨 앞 부분 문자열 과 특 정 구간부터 맨 끝 까지 부분 문자열(suffix)가 일치하다는 것이고 같은 substring(prefix, suffix)가 두 개라는 걸 손 쉽게 알 수 있습니다. 

 

그래서 답은 pattern의 pi 부분 일치 테이블 중 max값을 반환하면 됩니다......

 

 

이렇게 제출했는데 틀렸습니다.

하루정도 생각을 하고 나니..

kmp의 pi배열은 정말 prefix == suffix인 경우에만 일치 카운트를 증가시킨다는 점입니다. pi 배열의 특정 값이 증가한다는 것의 모든 시작은 문자열의 맨 처음...

 

pattern: abbbbcbbbba

이 경우,

pi배열의 prefix는 무조건 a부터 시작합니다.

abbbbcbbbba

  abbbbc ( 0 : b!=a이니까 pi테이블의 pi[1] = 0 )

 

ab가 있을 때 suffix = b.

prefix = a.

---

abbbbcbbbba

    ab ( 0 :b!=a이니까 pi테이블의 p[2] = 0)

 

abb가 있을 때

suffix는 b.

prefix = a.

...

abbbbcbbbba

                      ab... ( 1 : a == a이니까 pi테이블의 p[10] = 1 )

그리고 pi 테이블에서 가장 큰 prefix == suffix는 1입니다. Substring이 bbbb인 경우엔 뒤에도 bbbb가 있습니다. 하지만 kmp알고리즘의 특징은 prefix가 a로 시작하고 가장 연속 일치하는 부분을 구한pi 부분 일치 테이블에서 긴 구간의 첫 일치 index를 시작 위치로 잡는 것입니다.

 

그래서 abbbbcbbbba의 pi배열에서 suffix의 시작은 b가 될수 없고 오직 a로 시작됩니다. prefix와 suffix를 비교해가니까요.

 

 

 

만약 a가 없는 bbbbcbbbba에선 pi테이블이 달라질 것입니다.

 

 

오늘 또 이 문제를 통해 kmp알고리즘에서 사용되는 pi 테이블의 특징을 한가지 알게 됬습니다. 

 

이 문제의 결론: pattern에서 맨 앞 문자를 제거해 나가면서 prefix 시작 위치를 바꾼 후 pi 테이블을 통해 prefix==suffix를 구한다면 더 긴 prefix == suffix를 찾을 수 있다는 점입니다.

코드

 

func getPartialMatch(needle: [String]) -> [Int] {
    var pi = Array(repeating:0,count: needle.count)
    var begin = 1, matched = 0
    while begin + matched < needle.count {
        if needle[begin+matched] == needle[matched] {
            matched += 1
            pi[begin+matched-1] += matched
        } else {
            if matched == 0 {
                begin += 1
            }else{
                begin += matched - pi[matched-1]
                matched = pi[matched-1]
            }
        }
    }
    return pi
}
var pattern = readLine()!.map{String($0)}
var res = 0
_=(0..<pattern.count).map {
    let substring = pattern.suffix(pattern.count-$0).map{$0}
    let pi = getPartialMatch(needle: substring)
    res = max(res,pi.max()!)
}
print(res)