CF25ETest

Điểm: 99,00

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 64M

Input: stdin

Output: stdout

Tác giả:

txhai12

Dạng bài

Ngôn ngữ cho phép

C, C++

Nguồn đề : https://www.spoj.com/problems/CF25E/

Cho ba chuỗi $s_{1}, s_{2}, s_{3}$ , tính độ dài của chuỗi kí ngắn nhất có chứa cả 3 chuỗi trên.

Input

Dòng 1: t - số lượng test $(1 <= t <= 10^{3})$

Mỗi 3t dòng tiếp theo : chứa lần lượt $s_{1}, s_{2}, s_{3}$ trên mỗi dòng. $(1 <= l e n (s_{i}) <= 10^{5})$ , $s_{i}$ chỉ chứa các chữ cái thường. ('a'->'z')

Tổng độ dài các chuỗi không vượt quá $3 * 10^{6}$

Kết quả

Độ dài của chuỗi kí ngắn nhất có chứa cả 3 chuỗi trên.

20 test đầu : 40đ - $1 <= l e n (s_{i}) <= 10^{3}$

30 test sau : 60đ - $1 <= l e n (s_{i}) <= 10^{5}$

Sample Input

Copy

2
ab
bc
cd
abacaba
abaaba
x

Sample Output

Copy

4
11

giải thích : xâu ngắn nhất có chứa cả 3 xâu "ab", "bc", "cd" là xâu "abcd" có độ dài là 4.

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

huykhanh đã bình luận 2:41:29 ch, 28/07/2021

bài này t số lượng test có giới hạn t khoảng bao nhiêu không các anh ơi

0

txhai12 đã bình luận 4:11:22 ch, 28/07/2021

10^3 em nhé, anh vừa bổ sung luôn r