[BOJ 16570] 앞뒤가 맞는 수열

KMP 문제

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

 

KMP 실패 함수 응용 문제입니다.

---

[문제 풀이]

 

앞에서부터 수열을 잘라가면서 접두부와 접미부가 일치하는 최대 길이와 그 길이가 가능한 방법의 수를 구하는 문제입니다.

 

아주 간단하게 생각해보면 수열을 앞에서부터 하나씩 자르면서 자른 수열의 앞뒤가 같은지 비교하고, 앞뒤가 다르다면 제일 앞의 수를 또 자르고 비교(생략)하면 됩니다.

그러나 이렇게 푼다면 앞에서부터 잘린 수열의 개수 N개에 대해 수열의 앞뒤를 비교하게 되는데, 1 1 1 ... 1과 같이 수열의 모든 요소가 같다면 위의 생략 과정이 없어지기에 시간복잡도는 $O(N^2)$이 됩니다.

N이 1,000,000이니 당연히 시간 초과입니다.

 

접두, 접미에 관한 내용이 나오니 실패 함수로 접근하고 싶기는 한데, 이 문제는 여의치 않습니다.

앞의 문자열을 하나씩 잘라가면서 실패 함수를 계속 만들면 시간복잡도는 마찬가지로 O(N^2)입니다.

심지어 평균적인 상황에서는 아주 간단하게 생각한 위의 코드보다도 느릴 겁니다.

 

 

이 문제에서 주목해야 할 점이 있습니다.

수열을 무조건 앞에서부터 자르므로 수열을 잘라내면서 계속 접두부 접미부를 비교할 때마다 접미부는 그대로라는 점입니다.

만약 접두부가 그대로였다면 어땠을까요?

단순한 실패 함수 문제가 됩니다.

 

이 문제는 앞부분을 자른다는 조건으로 $O(N^2)$ 문제인 척 위장했지만 사실은 뒤에서부터 실패 함수를 만드는 문제입니다.

뒤에서부터 실패 함수를 만들면서 한 번도 실패 테이블에 값이 갱신이 안 됐다면 -1을 출력하고, 아니라면 실패 테이블의 최댓값과 그 최댓값이 몇 개가 있는지 출력하면 됩니다.

 

---

[소스 코드] / C++

 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int arr[1000000];
int table[1000000];

pair<int, int> makeTable(int N) {
    int ans = 0, count = 0;

    int j = 0;
    for (int i = 1; i < N; i++) {
        while (j > 0 && arr[i] != arr[j]) {
            j = table[j - 1];
        }

        if (arr[i] == arr[j]) {
            table[i] = ++j;

            if (j >= ans) {
                if (j > ans) {
                    ans = j;
                    count = 0;
                }
                ++count;
            }
        }
    }

    return make_pair(ans, count);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N; cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    reverse(arr, arr + N);

    pair<int, int> ans = makeTable(N);

    if (ans.first == 0) {
        cout << -1;
    } else {
        cout << ans.first << ' ' << ans.second;
    }
    
    return 0;
}