백준 4354번: 문자열 제곱

Seungil Kim·2022년 5월 5일
0

PS

목록 보기
196/206

문자열 제곱

백준 4354번: 문자열 제곱

아이디어

실패함수에서 f[s.length-1]은 가장 긴 접두사이면서 접미사의 길이이다. 우리가 구하는 n은 s.length/(s.length-f[s.length-1])이다. 이 때 ABCAB같은 반례가 있기 때문에 나누어 떨어지는 경우에만 n으로 채택하도록 하자.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 1e6+10;
int fail[MAX];

void make_fail(string& s) {
    int begin = 1, match = 0;
    while (begin + match < s.length()) {
        if (s[begin+match] == s[match]) {
            match++;
            fail[begin+match-1] = match;
        }
        else {
            if (!match) begin++;
            else {
                begin += match - fail[match-1];
                match = fail[match-1];
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    while (1) {
        string s;
        cin >> s;
        if (s == ".") break;
        memset(fail, 0, sizeof(fail));
        make_fail(s);
        if (s.length()%(s.length()-fail[s.length()-1])) cout << 1 << '\n';
        else cout << s.length()/(s.length()-fail[s.length()-1]) << '\n';
    }

    return 0;
}

여담

KMP 넘 어렵다.. 아직도 이해가 잘 안된다.
많이 풀어봐야겠다.

profile
블로그 옮겼어용 https://ks1ksi.io/

0개의 댓글