Biến đổi xâu


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 98M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Với mỗi xâu ký tự \(X\) ta có thể thực hiện các thao tác sau đây:

  • Xoá một ký tự ở vị trí bất kỳ
  • Chèn thêm một ký tự vào vị trí bất kỳ
  • Thay thế một ký tự bởi một ký tự khác ở vị trí bất kỳ.

Cho hai xâu ký tự \(X\) và \(Y\) hãy tìm cách biến đổi xâu \(X\) thành xâu \(Y\) với các thao tác ở trên sao cho số phép biến đổi là ít nhất.

Input

Dòng đầu là xâu \(X\) không quá \(1000\) ký tự in thường Tiếng Anh.

Dòng cuối là xâu \(Y\) không quá \(1000\) ký tự in thường Tiếng Anh.

Output:

Một số nguyên duy nhất là số phép biến đổi xâu ít nhất từ xâu \(X\) thành \(Y\).

Example

Input:

vo
chong

Output:

4

Giải thích: Có nhiều cách biến đổi 4 bước để chuyển xâu "vo" thành "chong" sau đây là một cách: "vo" -> "cvo" -> "cho" -> "chon" -> "chong".

tichpx

Comments

There are no comments at the moment.