3111 검열

3111 검열 https://www.acmicpc.net/problem/3111

1. T에 A가 없으면 알고리즘을 종료한다.
2. T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.
3. T에 A가 없으면 알고리즘을 종료한다.
4. T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.
5. 1번으로 돌아간다.

문자열 T와 단어A가 주어질 때 위의 알고리즘으로 남아있는 문자열을 구하는 문제이다.

문자열 폭발 문제와 유사하지만 맨앞과 맨뒤의 단어를 번갈아가며 지운다는 점이 다르다. 

문자열 폭발은 실시간으로 폭발이 일어날 경우가 생기면 바로바로 지워주는 반면에

이 문제는 먼저 전처리로 폭발이 일어나는 과정을 처리하며 남는것은 우선 스택2개에 각각 넣어준다.

예를들어 단어 A가 abc이고 T가 abcaabcbc가 있다고 하면 다음과 같은 과정이 될것이다.

전처리 이후의 두 스택을 이용해서 잘 해결하면 된다.

스택을 이용한다는 것보다는 전처리 이후에 처리한다는 구상을 떠올리기 어려운 문제였다.

#include <cstdio> #define max(a,b) ((a)<(b)?(b):(a)) #define min(a,b) ((a)<(b)?(a):(b)) template<typename T> struct stack {     T *arr;     int ptr;     stack() :ptr(0) { arr = new T[300055]; }     ~stack() { delete arr; }     void clear() {         ptr = 0;     }     void push(T data) {         arr[ptr++] = data;     }     void pop() {         ptr--;     }     T top() {         return arr[ptr - 1];     }     bool empty() {         return ptr == 0;     }     int size() {         return ptr;     } }; int N, M; char cmp[26]; char revcmp[26]; char str[300001]; int main() {     scanf("%s", &cmp);     scanf("%s", &str);     for (M = 0; cmp[M]; M++);     for (N = 0; str[N]; N++);     for (int m = 0; m < M; m++) revcmp[m] = cmp[M - m - 1];       stack<char> stk1, stk2;     int l = 0, r = N - 1;     int dir = 1;     while (l <= r && l < N && r >= 0) {         bool find = true;         if (dir) {             stk1.push(str[l]);             if (stk1.size() >= M) {                 for (int m = stk1.size() - M, t = 0; m < stk1.size(); m++, t++) {                     if (cmp[t] != stk1.arr[m]) {                         find = false;                         break;                     }                 }                 if (find) {                     for (int m = 0; m < M; m++) stk1.pop();                     dir ^= 1;                 }             }             l++;         }         else {             stk2.push(str[r]);             if (stk2.size() >= M) {                 for (int m = stk2.size() - M, t = 0; m < stk2.size(); m++, t++) {                     if (revcmp[t] != stk2.arr[m]) {                         find = false;                         break;                     }                 }                 if (find) {                     for (int m = 0; m < M; m++) stk2.pop();                     dir ^= 1;                 }             }             r--;         }     }     if (stk1.empty() && !stk2.empty()) {         for (int m = stk2.size() - 1; m >= 0; m--) printf("%c", stk2.arr[m]);         return 0;     }     if(!stk1.empty() && stk2.empty()) {         for (int m = 0; m < stk1.size(); m++) printf("%c", stk1.arr[m]);         return 0;     }       bool find = true;     while (find) {         if (stk1.size() + stk2.size() < M) break;         find = false;         for (int n = max(0, stk1.size() - M); n < stk1.size(); n++) {             int idx = 0, l = 0, r = 0;             for (int m = n; m < stk1.size(); m++, l++) {                 if (stk1.arr[m] == cmp[idx]) idx++;             }             for (int m = stk2.size() - 1; m >= 0 && l + r < M; m--, r++) {                 if (stk2.arr[m] == cmp[idx]) idx++;             }             if (idx == M && l + r == idx) {                 find = true;                 for (int m = 0; m < l; m++) stk1.pop();                 for (int m = 0; m < r; m++) stk2.pop();                 break;             }         }     }     for (int m = 0; m < stk1.size(); m++) printf("%c", stk1.arr[m]);     for (int m = stk2.size() - 1; m >= 0; m--) printf("%c", stk2.arr[m]);     return 0; } Colored by Color Scripter

cs