ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし

AOJ 1296: Repeated Substitution with Sed

はじめに

  • 解けるまでの時間: 25分
  • WA(TLE) 1回

問題

あなたはUnixsedコマンドというものがある。 これは入力した文字列を書き換えるコマンドである。 例えば、aabca に書き換えるsedaaxaaa という文字列に適用した場合、 書き換えた後の文字列は bcaxbcaa となる。 aaa の部分に関しては、aa の取り方が2パターン考えられるが、 このような場合は左から貪欲にマッチングされる。

(a, b) の組み合わせがn個と、s,tが与えられるので、 aをbにするsedを最低何回行えばsをtに変換できるか求めよ。

制約条件

  • nは10以下
  • a, b の長さは1以上10以下
  • |a| <= |b|
  • それぞれのaのはすべて異なる
  • s, t の長さは1以上10以下
  • |s| <= |t|
  • 文字列は英語小文字のみを含む

解法

  • 基本的に幅優先探索を行う
  • 変換の制約条件から、置換したら文字列が短くなることはない
  • 置換前と置換後で文字列が変化している
  • ↑の2つで枝刈り&「変換することができない」判定を行う
  • sedのシミュレートはJavaのreplaceAllを使うと楽

ソースコード

``java class Main { public static void main(String args) throws Exception { // System.out.println("aaxaaa".replaceAll("aa", "cba")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); while(true) { int n = Integer.parseInt(br.readLine()); if(n == 0) break; String sed = new String[n]; for(int i = 0; i < n; i++){ sed[i] = br.readLine().split(" "); } // ゴール String s = br.readLine(); String g = br.readLine(); System.out.println(bfs(s, g, sed)); } }

static int bfs(String s, String g, String[][] sed){
    if(s.equals(g)) return 0;
    int n = sed.length;

    // 最初の状態
    State startState = new State(s, 0);
    ArrayDeque<State> q = new ArrayDeque<State>();
    q.addLast(startState);
    // 幅優先探索
    while(q.size() > 0) {
        State state = q.pollFirst();
        for (int i = 0; i < n; i++) {
            String newStr = state.str.replaceAll(sed[i][0], sed[i][1]);
            // ゴールしていた場合
            if(newStr.equals(g)) {
                return state.count + 1;
            }
            // ゴールの文字列より長くならない, 元の文字列から変化している
            if(newStr.length() < g.length() && !newStr.equals(state.str)) {
                q.addLast(new State(newStr, state.count + 1));
            }
        }
    }
    return -1;
}

}