백준 1893번 : 시저 암호 - KMP

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

1893번: 시저 암호

 

#include <bits/stdc++.h>

using namespace std;

vector<int> getFail(const vector<int> &pattern) {
    int j = 0;
    vector<int> fail(pattern.size());
    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;
        }
    }

    return fail;
}


bool KMP(const vector<int> &pattern, const vector<int> &text) {
    vector<int> fail = getFail(pattern);

    int cnt = 0;
    int j = 0;
    for (int i = 0; i < text.size(); i++) {
        while (j > 0 && pattern[j] != text[i]) {
            j = fail[j - 1];
        }

        if (pattern[j] == text[i]) {
            if (j == pattern.size() - 1) {
                cnt++;
                j = fail[j];
            } else {
                j++;
            }
        }
    }

    return cnt == 1;
}


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

    int N;
    cin >> N;

    for (int t = 0; t < N; t++) {
        string A, W, S;
        cin >> A >> W >> S;

        vector<int> ans;

        map<char, int> charToInt;
        for (int i = 0; i < A.length(); i++) {
            charToInt[A[i]] = i;
        }

        int originPattern[W.length()];
        vector<int> text(S.length());

        //암호문 S를 숫자 배열로 변경
        for (int i = 0; i < S.length(); i++) {
            text[i] = charToInt[S[i]];
        }

        //W를 숫자 배열로 변경
        for (int i = 0; i < W.length(); i++) {
            originPattern[i] = charToInt[W[i]];
        }

        //W 모든 시프트 케이스 비교
        for (int i = 0; i < A.length(); i++) {
            vector<int> curPattern(W.length());

            for (int j = 0; j < W.length(); j++) {
                curPattern[j] = originPattern[j] + i;
                if (curPattern[j] >= A.length()) {
                    curPattern[j] -= A.length();
                }
            }


            //현재 패턴으로 케이스 비교
            if (KMP(curPattern, text)) {
                ans.push_back(i);
            }
        }

        //print
        if (ans.size() == 0) {
            cout << "no solution\n";
        } else if (ans.size() == 1) {
            cout << "unique: " << ans[0] << '\n';
        } else {
            cout << "ambiguous: ";
            for (auto a: ans) {
                cout << a << ' ';
            }
            cout << '\n';
        }
    }

    return 0;
}