[C++] 백준 10266 - 시계 사진(KMP 알고리즘, 문자열)

0. [c++] 백준

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

1. 풀이

2. 소스코드

#include <iostream>
#include <string>
#include <vector>
#include<deque>
#include<algorithm>
 
using namespace std;
 
int N;
int arr[200010];
deque<int> angle;
int arr2[400010];
deque<int> angle2;
 
//N에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용해 pi[] 계산
//pi[i] = N[,,i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이
 
//vector<int> getPartialMatch(const string &N)
//{
//    int M = N.size();
//    vector<int> pi(M, 0);
//
//    //KMP로 자기 자신을 찾는다
//    //N을 N에서 찾는다.
//    //begin=0이면 자기 자신을 찾아버리니까 안됨!
//    int begin = 1, matched = 0;
//    //비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록
//    while (begin + matched < M) {
//        if (N[begin + matched] == N[matched]) {
//            matched++;
//            pi[begin + matched - 1] = matched;
//        }
//        else {
//            if (matched == 0)
//                begin++;
//            else {
//                begin += matched - pi[matched - 1];
//                matched = pi[matched - 1];
//            }
//        }
//    }
//    return pi;
//}
 
vector<int> getPartialMatch()
{
    vector<int> pi(N, 0);
 
    //KMP로 자기 자신을 찾는다
    //N을 N에서 찾는다.
    //begin=0이면 자기 자신을 찾아버리니까 안됨!
    int begin = 1, matched = 0;
    //비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록
    while (begin + matched < N) {
        if (angle[begin + matched] == angle[matched]) {
            matched++;
            pi[begin + matched - 1] = matched;
        }
        else {
            if (matched == 0)
                begin++;
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}
 
//////코드 20.2 커누스-모리스-프렛(Knuth-Morris-Pratt) 문자열 검색 알고리즘의 구현
//
////'짚더미'H의 부분 문자열로 '바늘' N이 출현하는 시작 위치들을 모두반환한다.
//vector<int> kmpSearch(const string& H, const string& N) {
//    int n = H.size(), m = N.size();
//    vector<int> ret;
//    //pi[i]=N[..i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이
//    vector<int> pi = getPartialMatch(N);
//
//    //begin=matched=0에서부터 시작하자.
//    int begin = 0, matched = 0;
//    while (begin <= n - m) {
//        //만약 짚더미의 해당 글자가 바늘의 해당 글자와 같다면
//        if (matched < m && H[begin + matched] == N[matched]) {
//            ++matched;
//            //결과적으로 m글자가 모두 일치했다면 답에 추가한다.
//            if (matched == m) ret.push_back(begin);
//        }
//        else {
//            //예외: matched가 0인 경우에는 다음 칸에서부터 계속
//            if (matched == 0)
//                begin++;
//            else {
//                begin += matched - pi[matched - 1];
//                //begin을 옮겼다고 처음부터 다시 비교할 필요가 없다.
//                //옮긴 ㅎ에도 pi[matched-1]만큼은 항상 일치하기 때문이다.
//                matched = pi[matched - 1];
//            }
//        }
//    }
//
//    return ret;
//
//}
//
//
//
//////코드 20.7 KMP 알고리즘의 다른 구현
//
//vector<int> kmpSearch2(const string& H, const string& N) {
//    int n = H.size(), m = N.size();
//    vector<int> ret;
//    vector<int> pi = getPartialMatch(N);
//    //현재 대응된 글자의 수
//    int matched = 0;
//    //짚더미의 각 글자를 순회한다.
//    for (int i = 0; i < n; i++) {
//        //matched번 글자와 짚더미의 해당 글자가 불일치할 경우,
//        //현재 대응된 글자의 수를 pi[matched-1]로 줄인다.
//        while (matched > 0 && H[i] != N[matched])
//            matched = pi[matched - 1];
//        //글자가 대응될 경우
//        if (H[i] == N[matched]) {
//            matched++;
//            if (matched == m) {
//                ret.push_back(i - m + 1);
//                matched = pi[matched - 1];
//            }
//        }
//    }
//    return ret;
//}
 
bool kmpSearch2() {
    vector<int> pi = getPartialMatch();
    //현재 대응된 글자의 수
    int matched = 0;
    //짚더미의 각 글자를 순회한다.
    for (int i = 0; i < 2*N; i++) {
        //matched번 글자와 짚더미의 해당 글자가 불일치할 경우,
        //현재 대응된 글자의 수를 pi[matched-1]로 줄인다.
        while (matched > 0 && angle2[i] != angle[matched])
            matched = pi[matched - 1];
        //글자가 대응될 경우
        if (angle2[i] == angle[matched]) {
            matched++;
            if (matched == N) {
                return true;
            }
        }
    }
 
    return false;
}
 
 
int main(void)
{
    //데이터 입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> arr2[i];
    }
    //바늘의 위치를 각도로 변환
    sort(arr, arr + N);
    sort(arr2, arr2 + N);
 
    for (int i = 0; i < N - 1; i++) {
        angle.push_back(arr[i + 1] - arr[i]);
    }
    angle.push_back(360000 - arr[N - 1] + arr[0]);
 
    for (int i = 0; i < N-1; i++) {
        angle2.push_back(arr2[i + 1] - arr2[i]);
    }
    angle2.push_back(360000 - arr2[N - 1] + arr2[0]);
    for (int i = 0; i < N; i++) {
        angle2.push_back(angle2[i]);
    }
    
    if (kmpSearch2())
        cout << "possible";
    else
        cout << "impossible";
    return 0;
 
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!