結果
問題 | No.225 文字列変更(medium) |
ユーザー |
![]() |
提出日時 | 2015-06-12 22:29:45 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 45 ms / 5,000 ms |
コード長 | 3,895 bytes |
コンパイル時間 | 1,760 ms |
コンパイル使用メモリ | 109,568 KB |
実行使用メモリ | 22,272 KB |
最終ジャッジ日時 | 2024-12-24 09:42:00 |
合計ジャッジ時間 | 3,286 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.IO;using System.Collections.Generic;using System.Globalization;using System.Linq;using System.Text;partial class Solver {public static int EditDistance<T>(string A, string B) {return EditDistance(A.ToCharArray(), B.ToCharArray());}public static int EditDistance<T>(T[] A, T[] B) where T : IEquatable<T> {int n = A.Length;int m = B.Length;var dp = new int[n + 1, m + 1];for (int i = 0; i <= n; i++) {dp[i, 0] = i;}for (int i = 0; i <= m; i++) {dp[0, i] = i;}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (A[i].Equals(B[j])) {dp[i + 1, j + 1] = Math.Min(dp[i, j + 1], dp[i + 1, j]) + 1;dp[i + 1, j + 1] = Math.Min(dp[i + 1, j + 1], dp[i, j]);} else {dp[i + 1, j + 1] = Math.Min(dp[i, j + 1], dp[i + 1, j]) + 1;dp[i + 1, j + 1] = Math.Min(dp[i + 1, j + 1], dp[i, j] + 1);}}}return dp[n, m];}public void Run() {var n = ni();var m = ni();var s = ns();var t = ns();var d = EditDistance(s.ToArray(), t.ToArray());cout.WriteLine(d);}}// PREWRITEN CODE BEGINS FROM HEREpartial class Solver : Scanner {public static void Main(string[] args) {new Solver(Console.In, Console.Out).Run();}TextReader cin;TextWriter cout;public Solver(TextReader reader, TextWriter writer): base(reader) {this.cin = reader;this.cout = writer;}public Solver(string input, TextWriter writer): this(new StringReader(input), writer) {}public int ni() { return NextInt(); }public int[] ni(int n) { return NextIntArray(n); }public long nl() { return NextLong(); }public long[] nl(int n) { return NextLongArray(n); }public double nd() { return NextDouble(); }public string ns() { return Next(); }public string[] ns(int n) { return NextArray(n); }}public class Scanner {private TextReader Reader;private Queue<String> TokenQueue = new Queue<string>();private CultureInfo ci = CultureInfo.InvariantCulture;public Scanner(): this(Console.In) {}public Scanner(TextReader reader) {this.Reader = reader;}public int NextInt() { return Int32.Parse(Next(), ci); }public long NextLong() { return Int64.Parse(Next(), ci); }public double NextDouble() { return double.Parse(Next(), ci); }public string[] NextArray(int size) {var array = new string[size];for (int i = 0; i < size; i++) array[i] = Next();return array;}public int[] NextIntArray(int size) {var array = new int[size];for (int i = 0; i < size; i++) array[i] = NextInt();return array;}public long[] NextLongArray(int size) {var array = new long[size];for (int i = 0; i < size; i++) array[i] = NextLong();return array;}public String Next() {if (TokenQueue.Count == 0) {if (!StockTokens()) throw new InvalidOperationException();}return TokenQueue.Dequeue();}public bool HasNext() {if (TokenQueue.Count > 0)return true;return StockTokens();}private bool StockTokens() {while (true) {var line = Reader.ReadLine();if (line == null) return false;var tokens = line.Trim().Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);if (tokens.Length == 0) continue;foreach (var token in tokens)TokenQueue.Enqueue(token);return true;}}}