- T에 A가 없으면 알고리즘을 종료한다.
- T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.
- T에 A가 없으면 알고리즘을 종료한다.
- T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.
- 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;
}
| cs |
