BOJ 9935: 문자열 폭발 작성일 2020-03-07 https://www.acmicpc.net/problem/9935 3월동안 210문제 풀기 (16/210) 이것도 kmp로 어거지로 푼 문제. 정해는 스택으로 풀어야함. 내가 푼 방식대로 할 경우 저격데이터에 시간초과가 남 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include <bits/stdc++.h> using namespace std; vector<int> kmp(string& text, string& pattern) { vector<int> pi(pattern.size()), ans; for(int i = 1, k = 0; i < pattern.size(); i++) { while(k && pattern[k] != pattern[i]) k = pi[k-1]; if(pattern[k] == pattern[i]) pi[i] = ++k; } for(int i = 0, k = 0; i < text.size(); i++) { while(k && text[i] != pattern[k]) k = pi[k-1]; if(text[i] == pattern[k]) k++; if(k == pattern.size()) { ans.push_back(i-k+1); k = pi[k-1]; } } return ans; } int main() { ios::sync_with_stdio(false); string text, pattern; cin >> text >> pattern; while(1) { vector<int> pos = kmp(text, pattern); vector<pair<int,int>> seq; if (pos.empty()) break; for(int i = 0; i < pos.size(); i++) { int p = pos[i]; int size = pattern.size(); while(i < pos.size() && p+size == pos[i+1]) i++, size += pattern.size(); seq.push_back({p, size}); } for(auto& r : seq) { int& p = r.first; int& size = r.second; while(1) { int l = p-1; int r = p+size; int i, j; for(i = 0, j = 1; i < pattern.size()-1; i++, j++) if(text[l] == pattern[i] && text[r] == pattern[j]) break; while(l >= 0 && i >= 0 && text[l] == pattern[i]) l--, i--; while(r < text.size() && j < pattern.size() && text[r] == pattern[j]) r++, j++; if(i == -1 && j == pattern.size()) p = l+1, size += pattern.size(); else break; } } for(auto& r : seq) { int p = r.first; int size = r.second; for(int i = p; i < p+size; i++) text[i] = 0; } string newText; for(char c : text) if(c) newText += c; text = newText; } cout << (text.size() ? text : "FRULA"); }