P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P156SUME/

1. Đề bài P156SUME spoj

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”.

Bạn được cho 2 cho 2 chuỗi s1 và s2, hãy đếm xem chúng có tất cả bao nhiêu ước chung?

Input

Dòng đầu tiên là 1 chuỗi s1, dòng thứ 2 là chuỗi s2.

Cả 2 chuỗi đều gồm các chữ cái thường, độ dài 2 chuỗi không quá 105.

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:

1

 

Test 2:

Input:

aaa

aa

Output:

1

2. Hướng dẫn giải P156SUME spoj PTIT

– Gọi n1, n2 là độ dài của 2 xâu s1, s2.

– độ dài ước của xâu sẽ là [1..độ dài xâu], mà ở bài này ta cần xâu chung, như vậy ta chỉ cần xét các xâu có độ dài từ [1..min(n1,n2)]. và xâu có độ dài i có khả năng là ước của xâu khi n1 mod i=0 và n2 mod i = 0.

– Xét mỗi độ dài xâu ước, hãy kiểm tra xem xâu có độ dài i có phải là ước hay không? và kiểm tra ước trên s1, s2 giống nhau không.

– Đếm kết quả bài toán…

3. Code tham khảo P156SUME spoj PTIT

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *