[백준/Swift] 4354: 문자열 제곱 | PS일지

 

문제

4354번: 문자열 제곱

간단한 문제 요약

문자열 S가 주어졌을 때 어떤 문자열 a에 대해 s=a^n을 만족하는 가장 큰 n을 찾으시오. 

 

문자열 곱셈에 대해서

a^0 = "" (빈 문자열)

a^(n+1) = a*(a^n) 으로 정의 됩니다.

문제 풀이,  느낀점

"주어진 문자열S에서 어떻게 하면 부분 문자를 선정해 반복적으로 곱하면 S를 만들 수 있을까?.." 가장 유리한 것은 s문자열의 첫 문자부터 prefix로 하는 부분 문자열의 최소 길이를 찾으면 됩니다.

 

생각한 알고리즘으로 kmp알고리즘의 부분 일치 테이블을 이용하는 것인데(물론 알고리즘에서 kmp밖에 공부를 하지 않았다는 점..)

kmp 알고리즘의 부분 일치 테이블은 특정 pattern에서 prefix == suffix인 부분 일치를 찾는 것입니다. 그리고 문제에서 주어진 s = a^n 은 결국 부분 문자열 a를 몇 번 반복해야 s(원래 문자열)을 만들 수 있는지 최대 반복 n을 구하는 것입니다.

 

부분 일치 테이블 pi는 주어진 문자열 pattern에서 suffix, prefix가 같은 최대 길이를 담는 테이블입니다.

 

 

s = abcdabcd 일 때 

부분 일치 테이블 pi = [0,0,0,0,1,2,3,4] 입니다.

1,2,3,4가 나온 이유는 

abcdabcd 의 suffix _ _ _ _ abcd와

prefix abcd가 일치하기 때문입니다.

그리고 prefix == suffix == abcd입니다.

 

근데 중요한 것은 문자열 S의 suffix인 _ _ _ _ abcd는 뒷자리 abcd만 체크했습니다. 앞 부분 또한 체크를 해야 합니다. s문자열의 일부분일 때만 일치한다는 점을 발견했기 때문입니다.

 

만약 부분 일치 테이블 pi 의 마지막 원소가 0이라면 주어진 S에서는 자기자신을 제외하고 일치하는 부분 문자열로 s문자를 만들 수 있는 경우를 절대로 찾을 수 없습니다.

 

 

s = abcabcabc 일 때

 

부분 일치 테이블 pi = [0,0,0,1,2,3,4,5,6]입니다. prefix == suffix == abcabc를 사용해서 s문자열 suffix 부분은 일치한다는 사실을 알았습니다. 이제 확인할 것은 _ _ _ abcabc 언더바 3자리 앞부분입니다. 하지만 abcabc는 abc를 만들 수 없습니다. 결국 prefix == suffix인 suffix로는 s == suffix*n 를 만들수 있을 수도 없을수도 있다는 것을 알게 되었습니다.

 

하지만 여기서 신기한 점은 s문자열의 prefix' == suffix'인 suffix'가 1 이상일 때 s문자열의 prefix' 일부 또는 prefix'를 반복 사용해서  suffix'를 만들 수 있습니다. suffix'는 prefix'와 문자가 일치하기 때문입니다. prefix'의 앞 부분 문자를 사용할 때 반복 가능한 최소 위치가 될 수 있습니다.

 

 

부분 일치 테이블을 pi라고 했을 때 s.count - pi.last!길이인 s의 첫 부분 문자열 prefix를 반복하면 s문자열을 만들수 있습니다.

 

abcabcabc

000123456

9-6 = 3.

 

prefix abc를 3번 반복하면 abcabcabc를 만들 수 있습니다. 부분 일치 테이블의 suffix는 prefix==suffix인 prefix로 만들어지기 때문입니다.

하지만 s.count - pi.last!를 한 prefix를 여러 번 반복해도 s 문자를 구성할 수 없을 때가 있습니다.

 

ababcab

0012012

s.count - pi.last! = 5인 prefix = ababc.

 

이 prefix를 반복해도 s 문자열을 만들 수 없습니다.

 

부분 일치 테이블을 통해 1 이상의 prefix == suffix를 찾았을 때 prefix의 sub prefix를 반복 곱했을 때 원래의 s 문자열을 만들 수 있다는 사실.. 

 

s.count에서 s.count - pi.last!를 한 부분 prefix 길이로 나눴을 때 나누어 떨어진다면 부분 prefix를 반복 사용해서 s 문자열을 만들 수있고 그렇지 않고 나머지가 나올 경우 만들 수 없습니다. 

코드

func getPartialMatch(pattern: [String]) -> [Int] {
    var pi = Array(repeating: 0, count: pattern.count)
    var begin = 1, matched = 0
    
    while begin + matched < pattern.count {
        if pattern[begin+matched] == pattern[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
}

func solution() {
    var res = ""
    defer{ print(res) }
    while true {
        let text = readLine()!.map{String($0)}
        guard text.first != "." else { return }
        let pi = getPartialMatch(pattern: text)
        let prefix = text.count - pi.last!
        res += text.count % prefix == 0 ? "\(text.count/prefix)\n" : "1\n"
    }
}
solution()