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
chongOutput:
4Giả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".
Comments