[15501번] 부당한 퍼즐

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. kmp

2. 응용

이 문제는 왼쪽으로 스트링을 밀거나 오른쪽으로 밀거나 뒤집을 수 있다.

그렇다면 입력받은 string을 복사해보자.

1 2 3 4 5

라면

1234512345

로 만들어보자.

그리고 두번째로 확인할 문자열을 뒤집지 않은것과 뒤집을것을 생각해보자.

1 2 4 3 5

라면

12435
53421

이 될 것이다.

이 두개를 이제 위의 두번 복사한 곳에 있는지 확인해보고 둘중 하나라도 존재한다면 우리는 good puzzle임을 알 수 있다.

이때 존재하는지 확인은 kmp를 통해 간단히 확인 할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

#include <iostream> #include <cstdio> #include <vector> #include <string> #include <algorithm>   using namespace std;   vector<int> getPi(string p) {     int m = (int)p.size();     int j = 0;       vector<int> pi(m, 0);       for (int i = 1; i< m; i++) {         while (j > 0 && p[i] != p[j])             j = pi[j - 1];         if (p[i] == p[j])             pi[i] = ++j;     }     return pi; }   vector<int> kmp(string s, string p) {     vector<int> ans;     auto pi = getPi(p);     int n = (int)s.size(), m = (int)p.size(), j = 0;     for (int i = 0; i < n; i++) {         while (j>0 && s[i] != p[j])             j = pi[j - 1];         if (s[i] == p[j]) {             if (j == m - 1) {                 ans.push_back(i - m + 1);                 j = pi[j];             }             else {                 j++;             }         }     }     return ans; }   int main() {     int n;     scanf("%d", &n);       string vc ="";     for (int i = 0; i < n; i++)     {         int val;         scanf("%d", &val);         vc += val;     }     vc = vc + vc;     string tmp;     for (int i = 0; i < n; i++)     {         int val;         scanf("%d", &val);         tmp += val;     }       string revt = tmp;     reverse(revt.begin(), revt.end());     vector<int> a = kmp(vc, tmp);     vector<int> b = kmp(vc, revt);       printf("%s", (a.size() || b.size()) ? "good puzzle" : "bad puzzle");     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus