BOJ 9935: 문자열 폭발

작성일

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

  • 3월동안 210문제 풀기 (16/210)
  • 이것도 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
78
79
80
#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");
}