白駿9935号です.
https://www.acmicpc.net/problem/9935

質問する

尚根は文字列に爆発文字列を埋め込んだ.文字列が爆発すると、文字列から消え、残りの文字列が結合されます.
爆発は次の手順で行われます.

文字列に爆発文字列が含まれている場合、すべての爆発文字列が爆発します.残りの文字列を順番に接続し、新しい文字列を形成します.

新しく生成された

文字列には、爆発文字列が含まれる場合があります.

の爆発は、爆発文字列が文字列に含まれないまで続く.

尚根は爆発が終わった後に残った文字列をすべて求めてみた.時々残った文字がない.「FRULA」が出力されます.
爆発文字列には、2つ以上の同じ文字は含まれません.

入力

最初の行には文字列があります.文字列の長さは1以上で、1000000以下です.
2行目は爆発文字列を示します.長さは1以上36未満です.
どちらの文字列も小文字と大文字、数字0,1,...、9だけで構成されています.

しゅつりょく

最初の行は、爆発が終了した後に残ったすべての文字列を出力します.

入力例

mirkovC4nizCC44
C4

12ab112ab2ab
12ab

サンプル出力

mirkovniz

FRULA

考える

最初は、文字列を1つずつ巡回しながら、すべての爆発文字列を削除する方法を選択しました.問題はタイムアウトです.
タイムアウトは問題で、解決のためにいろいろ努力しましたが、結局失敗して、他の人のコードを参考に解読しました.
この問題はstackを用いて解決する必要がある.

アクション

		String str = br.readLine();
		String bomb = br.readLine();
		int str_len = str.length();
		int bomb_len = bomb.length();

タイムアウトはよく使われる方法で、長さの計算は事前に変数に設定しておきます.できるだけ時間を節約する.

	Stack<Character> stack = new Stack<>();

		for(int i=0; i<str_len; i++) {
			int count = 0;
			stack.push(str.charAt(i));

			// 스택의 크기가 폭탄 문자열의 길이와 같아지면 탐색 시작
			if(stack.size() >= bomb_len) {

				for(int j=0; j<bomb_len; j++) {

					if(stack.get(stack.size() - bomb_len + j) == bomb.charAt(j)) {
						count++;
					}	

					if(count == bomb_len) {
						for(int k=0; k<bomb_len; k++) {
							stack.pop();
						}
					}

				}
			}
		}

スタックのデータ構造を使用して、スタックのサイズがbombより大きい場合は、bomb文字列と同じようにスタック内のデータを繰り返しチェックします.popを実行します.

コード#コード#

import java.util.*;
import java.io.*;

public class Main {	

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		String str = br.readLine();
		String bomb = br.readLine();
		int str_len = str.length();
		int bomb_len = bomb.length();

		Stack<Character> stack = new Stack<>();

		for(int i=0; i<str_len; i++) {
			int count = 0;
			stack.push(str.charAt(i));

			// 스택의 크기가 폭탄 문자열의 길이와 같아지면 탐색 시작
			if(stack.size() >= bomb_len) {

				for(int j=0; j<bomb_len; j++) {

					if(stack.get(stack.size() - bomb_len + j) == bomb.charAt(j)) {
						count++;
					}	

					if(count == bomb_len) {
						for(int k=0; k<bomb_len; k++) {
							stack.pop();
						}
					}

				}
			}
		}

		if(stack.isEmpty()) {
			System.out.println("FRULA");
		}
		else {
			for(char ch : stack) {
				sb.append(ch);
			}
		}

		System.out.println(sb);
		
	} // End of main
} // End of class