| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P181PROG - ROUND 1G - K xâu con chung dài nhất |
Cho xâu s có độ dài n.
Một xâu con của xâu s bắt đầu ở vị trí l và kết thúc ở vị trí r (1 ≤ l ≤ r ≤ n) là xâu gồm dãy các kí tự liên tiếp sl, sl+1, sl+2, … , sr. Một xâu t được gọi là xuất hiện trong xâu s nếu t là xâu con của s.
Cho hai xâu a và b. Đầu tiên ta tìm một xâu xuất hiện trong cả a và b, giả sử nó kết thúc ở vị trí ra trong xâu a, rb trong xâu b. Sau đó ta tiếp tục tìm kiếm thêm xâu tiếp theo cũng xuất hiện trong cả 2 xâu a và b, nhưng vị trí bắt đầu của nó trong xâu a lớn hơn ra và trong xâu b lớn hơn rb. Như vậy ta thu được 2 xâu, lại tiếp tục tìm xâu thứ 3 sao cho nó xuất hiện sau xâu thứ 2 trong cả 2 xâu a và b … Cứ như vậy cho đến khi ta tìm được k xâu.
2 xâu a và b có độ dài lần lượt là m và n, số xâu cần tìm là k. Tìm tổng độ dài lớn nhất có thể có của k xâu tìm được theo cách trên.
Input
Dòng đầu tiên gồm 3 số m, n, k (1 ≤ m, n ≤ 1000, 1 ≤ k ≤ 10).
Dòng thứ hai chứa xâu a.
Dòng thứ ba chứa xâu b.
Các kí tự trong xâu chỉ gồm các chữ cái tiếng Anh in thường.
Output
Một dòng duy nhất là tổng độ dài lớn nhất có thể có của k xâu tìm được.
Dữ liệu đảm bảo luôn tìm được k xâu theo cách tìm trên.
Example
Input:
11 6 2
autumncloud
acloud Output: 6
Input:
16 25 2
adlkbapycyzeoyuh
mifdlkbioevxzzcyzeoryuxjg
Output:
9
Giải thích:
Ví dụ 1: autumncloud acloud
Ví dụ 2: adlkbapycyzeoyuh mifdlkbioevxzzcyzeoryuxjg
| Được gửi lên bởi: | adm |
| Ngày: | 2018-03-02 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
