백준 11585번: 속타는 저녁 메뉴

Seungil Kim·2022년 5월 6일
0

PS

목록 보기
197/206

속타는 저녁 메뉴

백준 11585번: 속타는 저녁 메뉴

아이디어

문자열을 두 개 이어 붙인 다음 거기서 찾으면 한바퀴 돌리면서 찾는거랑 똑같음. 이 때 처음부터 끝까지 찾으면 하나 더 찾을수도 있으므로 한칸 건너 뛴다. ex) ABCABC에서 ABC 찾기

코드

#include <bits/stdc++.h>

using namespace std;

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

int gcd(int a, int b) {
    if (!b) return a;
    return gcd(b, a%b);
}

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);

    int n;
    cin >> n;         
    string s, s2;
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        s += c;
    }
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        s2 += c;
    }
    s2 += s2;
    memset(fail, 0, sizeof(fail));
    make_fail(s);

    vector<int> v;
    // s2에서 s찾기
    int begin = 1, match = 0;
    while (begin + match < s2.length()) {
        if (match < s.length() && s2[begin+match] == s[match]) {
            match++;
            if (match == s.length()) v.push_back(begin);
        }
        else {
            if (!match) begin++;
            else {
                begin += match - fail[match-1];
                match = fail[match-1];
            }
        }
    }

    cout << v.size()/gcd(v.size(), n) << '/' << n/gcd(v.size(), n);

    return 0;
}

여담

오늘 저녁 짬이 뭐더라..

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

0개의 댓글