[伯俊]#1013 Contact

質問する

無限に広がる宇宙に人間だけが一人でいるとしたら、それは本当に悲しいことではないでしょうか.
プエルトリコのアレシボにあるアレシボ望遠鏡(Arecbo radio望遠鏡)は、数十年も存在しない可能性のある外部文明からの電波を受信するため、夜空を眺めている.
この望遠鏡で収集された電波の中で、自然に起こりにくいパターンを見つけ、これを証拠に外星文明の存在を判断しようとする努力が続いているが、まだ発見されていない.韓国天文学界のプライドである金ドンヒョク博士は、国内技術でこのような探査を行うために、以下の電波標識を基準にしている.
伝播の基本単位は,{0,1},x+()が任意の数(少なくとも1つ)xの繰返しからなる伝播の集合を表す2つの構成からなる.
(xyx)+()は括弧内のxyxの繰返し伝搬の集合である.以下に、理解を助ける例を示します.

1+ = { 1, 11, 111, 1111, 11111, … }

10+ = { 10, 100, 1000, 10000, 100000, … }

(01)+ = { 01, 0101, 010101, 01010101, 0101010101, … }

(1001)+ = { 1001, 10011001, 100110011001, … }

10+11 = { 1011, 10011, 100011, 1000011, 10000011, … }

(10+1)+ = { 101, 1001, 10001, 1011001, 1001101, 100011011000001, … }

重複を表す+のほか、DORを表す|記号もあります.{x|y}はxまたはyを表し、{0+|1+}は{0、1、00、11、000、111、...}の集合を表す.次に、2つのシンボルを複合して使用する例を示します.

(100 | 11)+ = { 100 , 11 , 10011 , 11100 , 1110011100 , 100111111100100, … }

最近、金ドンヒョク博士はアレシボ望遠鏡で星維加(織姫)から受信した一部の電波記録を調べ、電波のパターンを分析し、以下のように記録した.

(100+1+ | 01)+

金ドンヒョク博士は、様々な伝播記録から、このようなパターンを持つ伝播プログラムを見つける必要がある.この操作を実行できるプログラムを作成します.

入力

入力された第1行は、試験例の個数Tを与える.次の行から、各テストケースについて、伝播を表す{0,1}のみを含む文字列にスペースはありません.文字列長は(1≦N≦200)です.

しゅつりょく

各テストケースについて,与えられた伝播パターンが問題で提案されたパターンであり,「YES」でなければ「NO」が出力される.出力文字列はすべて大文字で構成されています.

入力例1

3
10010111
011000100110001
0110001011001

サンプル出力1

NO
NO
YES

に答える

この問題は正規表現で解くことができる.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Pattern pattern = Pattern.compile("^(100+1+|01)+$");
        Matcher matcher;

        for(int i=0; i<N; i++) {
            String input = br.readLine();
            matcher = pattern.matcher(input);

            if(matcher.matches())
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}