猫でもわかるWebプログラミングと副業

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

AOJ 1296: Repeated Substitution with Sed

はじめに

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

問題

あなたはUnixにsedコマンドというものがある。 これは入力した文字列を書き換えるコマンドである。 例えば、aabca に書き換えるsedを aaxaaa という文字列に適用した場合、 書き換えた後の文字列は 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;
}

}