[백준/C++] 16570번 앞뒤가 맞는 수열

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

16570번: 앞뒤가 맞는 수열

완탐하면 당연히 시간초과다.

그렇다면 어떻게 푸냐? 거꾸로 뒤집으면 된다. 수열을 거꾸로 입력받아서 그것에 대한 실패함수를 구하고, 최댓값과 최댓값이 나오는 횟수를 구해주면 된다.

근데 같은 방식인 것 같은데, 아래 코드와 정답 코드의 차이가 뭔 지 모르겠다. (더보기 클릭ㄱㄱ)

얘는 틀렸다고 한다.. why?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> v;
int maxi=-1,cnt;

vector<int> failure(string pattern){
    int j=0;
    vector<int> fail(pattern.size());
    // pi 배열은 접두사 접미사가 일치하는 최대 길이 구하기
    for(int i = 1; i < pattern.size() ; i++){
        while(j > 0 && pattern[i] != pattern[j]) { // 다르면
            j = fail[j - 1]; // 일치하는 부분까지 인덱스를 앞당김
        }
        if(pattern[i] == pattern[j]) {
            fail[i] = ++j; // 접두 접미사가 일치하는 최대 길이 저장
        }
        else{
            fail[i]=0;
        }
        maxi = max(maxi,fail[i]);
    }
    return fail;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    string s;
    cin >> n;
    for(int i=0;i<n;i++){
        int num;
        cin >> num;
        v.push_back(num);
    }
    for(int i=0;i<n;i++){
        s += to_string(v.back());
        v.pop_back();
    }
    vector<int> f = failure(s);
    for(int i=1; i<f.size();i++){
        if(f[i] == maxi) cnt++;
    }
    if(maxi ==0){
        cout << -1;
    }
    else {
        cout << maxi << ' ' << cnt;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> v;
int maxi=-1,cnt;

vector<int> failure(vector<int> pattern){
    int j=0;
    vector<int> fail(pattern.size());
    // pi 배열은 접두사 접미사가 일치하는 최대 길이 구하기
    for(int i = 1; i < pattern.size() ; i++){
        while(j > 0 && pattern[i] != pattern[j]) { // 다르면
            j = fail[j - 1]; // 일치하는 부분까지 인덱스를 앞당김
        }
        if(pattern[i] == pattern[j]) {
            fail[i] = ++j; // 접두 접미사가 일치하는 최대 길이 저장
        }
        else{
            fail[i]=0;
        }
        maxi = max(maxi,fail[i]);
    }
    return fail;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    string s;
    cin >> n;

    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin >>v[n-1-i];
    }
    vector<int> f = failure(v);
    for(int i=1; i<f.size();i++){
        if (maxi < f[i]) {
            maxi = f[i];
            cnt = 1;
        }
        else if (maxi == f[i]) {
            cnt++;
        }
    }
    if(maxi ==0){
        cout << -1;
    }
    else {
        cout << maxi << ' ' << cnt;
    }
    return 0;
}