9935 - 문자열 폭발

문제 링크

---

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

문제 요약

---

문자열 \(A\), \(B\)가 주어진다. \(B\)는 \(A\)안에서 연쇄적으로 사라질 때 최종적으로 남은 문자열이 무엇인지 출력하는 문제다.

문제 풀이

---

문자열이 연쇄적으로 사라진다는 점에 착안해서 \(A\)문자열을 앞에서부터 한 글자씩 답 문자열에 추가해 가면서 끝에서 \(B\)와 매칭이 되는가를 매번 확인해 준다. 

매번 확인하면 시간내에 들어올까 하는 의문이 생길수도 있다. 하지만 \(A\)의 길이가 \(10^6\)데 비해 \(B\)의 길이는 최대 \(36\)밖에 안되기 때문에 매우 빠른속도에 통과하는것을 확인할 수 있다.

시간복잡도는 \(O(|A||B|)\)이다.

소스 코드

---

#include <stdio.h>
#include <string.h>

int n, m, pos;
char A[1000010], B[40], ans[1000010];

bool isMatching(int s) {
  for (int i = s ; i < s + m ; ++i) {
    if (ans[i] != B[i - s]) {
      return false;
    }
  }
  return true;
}

int main() {
  scanf("%s%s", A, B);
  n = (int)strlen(A);
  m = (int)strlen(B);
  for (int i = 0 ; i < n ; ++i) {
    ans[pos++] = A[i];
    if (pos - m >= 0 && isMatching(pos - m)) {
      pos -= m;
    }
  }
  ans[pos] = '\0';
  printf("%s\n", pos ? ans : "FRULA");
}