「みんなのプロコン」本選 オープンコンテスト
A.YahooYahooYahoo(400)
問題
文字列 S が与えられる。yahooの文字列を0個以上繰り返してできる文字列との編集距離を求めよ。
- 1 <= |S| <= 105
方針
ポイントは大きく2つ。他は普通の編集距離DPと変わらない(遷移については通常の編集距離と同じである)
- 取るべき状態数が限定されていることに気づくこと
- yahoo -> yahoo と遷移がループする
1. 取るべき状態数が限定されていることに気づくこと
編集先の文字列は yahoo の文字のループであるので、配列としては yahoo の 5文字分あればいい。yahooyahooyahoo となる場合は mod 5 の index を使用する。
2.yahoo -> yahoo と遷移がループする
例えば yahooahoo との編集距離を考えると、以下のようになる。
1回目の遷移結果をもとに更新するパターンがあるためである。よって2回ループさせる必要がある。
public void solve(int testNumber, InputReader in, PrintWriter out) { String src = in.nextString(); int n = src.length(); String tar = "oyaho"; int[][] dp = new int[n+1][5]; for (int i = 0; i < n+1; i++) { Arrays.fill(dp[i], INF); } for (int i = 0; i < n+1; i++) { dp[i][0] = i; } for (int i = 0; i < 5; i++) { dp[0][i] = i; } for (int i = 1; i < n+1; i++) { for (int j = 1; j < 10; j++) { // 左 dp[i][j%5] = min(dp[i][(j-1)%5]+1, dp[i][j%5]); // 上 dp[i][j%5] = min(dp[i-1][j%5]+1, dp[i][j%5]); // 左上 int c = tar.charAt(j%5) == src.charAt(i-1) ? 0 : 1; dp[i][j%5] = min(dp[i-1][(j-1)%5]+c, dp[i][j%5]); } } out.println(dp[n][0]); }
雑記
ループする場合には状態数が抑えられる。