Posts CF.A.32. Mahmoud and Longest Uncommon Subsequence
Post
Cancel

CF.A.32. Mahmoud and Longest Uncommon Subsequence

(http://codeforces.com/contest/766/problem/A)

Mahmoud và Ehab luyện tập để thi HSG tin, một trong những bài toán cổ điển là "Xâu con chung dài nhất LCS", họ đã giải quyết bài đó một cách dễ dàng. Ehab đố bạn một bài toán khác gọi là "Xâu không chung dài nhất"

Cho hai xâu a, b. Hãy tìm xâu con không là xâu chung của hai xâu mà có độ dài lớn nhất? Một xâu được gọi là xâu con của s nếu nó chứa các kí tự trong s theo đúng thứ tự xuất hiện trong xâu s: ví dụ xâu "abc" có các xâu con là "a", "b", "c", "ab", "ac", "abc" trong khi xâu "acb" không phải là xâu con. Một xâu rỗng là xâu con của mọi xâu; xâu s là xâu con của chính nó.

Input:

  • Gồm hai dòng, dòng đầu ghi xâu a, dòng thứ hai ghi xâu b; cả hai xâu không rỗng, chỉ chứa kí tự Latin thường, có độ dài không quá 10^5

Output:

  • Nếu không tồn tại xâu con không chung in "-1" ngược lại in ra độ dài xâu con không chung lớn nhất?

Ví dụ:

InputOutput
abcd
defgh
5
a
a
-1
This post is licensed under CC BY 4.0

Trending Tags

Contents

Trending Tags