백준[13506] 카멜레온 부분 문자열

문제 설명

풀이

z알고리즘을 이용하여 풀이했습니다.

prefix이면서 suffix이고 그 위치가 아닌 곳에서 한번 더 나와야 합니다. 

이 조건을 만족하려면 Z[N-i] = i 이면 prefix이면서 suffix이고 중간 위치에 한번 더 나오기 위해서 Z[j] >= i (0 < j < N - i)인 j가 존재해야한다. 이때  j가 존재하는지 빠르게 확인하기 위해 pmax[i] : 0~ i까지의 최댓 값을 전처리해 O(1)만에 j가 존재하는지 확인 할 수 있도록 만든다.

코드

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

using namespace std;

int Z[1000006], pmax[1000006];

int main() {
    string s; cin >> s;
    int N = s.size();
    int L = 0, R = 0;
    for (int i = 1; i < N; i++) {
        if (i > R) {
            L = R = i;
            while (R < N && s[R - L] == s[R]) R++;
            Z[i] = R - L; R--;            
        } else {
            int k = i - L;
            if (Z[k] < R - i + 1) Z[i] = Z[k];
            else {
                L = i;
                while (R < N && s[R - L] == s[R]) R++;
                Z[i] = R - L; R--;
            }
        }
    }
    int M = 0;
    for (int i = 1; i < N; i++) {
        M = max(Z[i], M);
        pmax[i] = M;
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (Z[N - i] == i) {
            if (pmax[N - i - 1] >= i) ans = max(ans, i);
        }
    }
    if (ans) cout << s.substr(0, Z[N - ans]);
    else printf("-1");
}