Ước chung của chuỗi

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Một chuỗi \(a\) được gọi là ước của chuỗi \(b\) nếu tồn tại một số nguyên dương \(x\) sao cho khi ta viết \(x\) lần chuỗi \(a\) thì sẽ thu được chuỗi \(b\).

Ví dụ chuỗi abab có 2 ước là ab và abab.

Yêu cầu: Bạn được cho 2 chuỗi \(S_1\) và \(S_2\), hãy đếm xem chúng có tất cả bao nhiêu ước chung?

Input

Dòng đầu tiên chứa chuỗi \(S_1\).
Dòng thứ hai chứa chuỗi \(S_2\).
Cả 2 chuỗi đều gồm các chữ cái thường, độ dài 2 chuỗi không quá \(10^5\) ký tự.

Output

In ra một số nguyên là kết quả của bài toán.

Example

Test 1

Input

xyztxyzt  
xyzt

Output

Note

Chuỗi xyztxyzt có 2 chuỗi ước là: xyzt và xyztxyzt; Chuỗi xyzt có 1 chuỗi ước là: xyzt nên có 1 chuỗi ước chung là xyzt

Test 2

Input

aaaa
aa

Output

Note

Chuỗi aaaa có 3 chuỗi ước là: a, aa và aaaa; Chuỗi aa có 2 chuỗi ước là: a và aa nên có 2 chuỗi ước chung là a và aa

Bình luận

-33

Lê_Gia_Khánh 11:02 p.m. 14 Tháng 5, 2020

Sai chính tả tè le kìa thầy :))

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

-33

NguyenHuuNhatQuang 4:15 p.m. 16 Tháng 5, 2020

Lỗi cơ bản sai mấy lần

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

1 bình luận nữa