[백준] 10747 Censoring

문자열 S에서 T가 나오는동안 다 지우고 남은 문자열을 출력하는 문제다

계속 틀렸따 푸는 방법을 알았는데도 코딩을 못해서 계속틀렸다

푸는 방법은 KMP로 S에서 T를 찾다가 찾으면 바로 제거하고 남은부분을 다시 KMP하는 방법이다! 이걸 다른곳에서 만나면 또 틀릴것같다

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
char ans[1000011];
int top;
vector<int> preprocessing(string & s) {
    int n = s.size();
    int j = 0;
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) pi[i] = ++j;
    }
    return pi;
}
void kmp(string &s, string&p) {
    int n = s.size();
    int m = p.size();
    int j = 0;
    vector<int> pi = preprocessing(p);
    vector<int> kmpi(n,0);
    for (int i = 0; i < n; i++) {
        while (j > 0 && s[i] != p[j]) j = pi[j - 1];
        if (s[i] == p[j]) j++;
        ans[++top] = s[i];
        kmpi[top] = j;
        if (j == m) {
            top -= m;
            j = kmpi[top];
        }
    }
}
 
int main() {
    string s, t; cin >> s >> t;
    kmp(s, t);
    ans[top+1] = 0;
    cout << (ans+1) << "\n";
}